solution-2022 CCPC Guilin J. Permutation Puzzle

WRuperD · 2024-08-21 15:08:35 · 题解

题解：2022 CCPC 桂林站 J 题题解

模拟赛 T3 放了这道题人均场切了。我没删调试爆零了。

首先按所有限制连边 u_i \to v_i。题目保证了这是一张有向无环图。

我们肯定是只能按照某种拓扑序来填。

有一个非常显然的策略是在拓扑排序中按照每个点的后继节点的最小值为第一关键字，更小的先填。

这非常符合直觉，也确实是对的。因为无论如何你都要在当前最小值之前到那。

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define int long long
#define pb emplace_back
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');}
#define put() putchar(' ')
#define endl puts("")
const int MAX = 2e5 + 10;

vector <int> g[MAX];
vector <int> g2[MAX];
bool vis[MAX];
int a[MAX];

void dfs(int u){
    vis[u] = 1;
    for(int v : g[u]){
        if(!vis[v]) dfs(v);
        a[u] = min(a[u], a[v]);
    }
}

int deg[MAX];
int deg2[MAX];
int b[MAX];
int to[MAX];
bool fl[MAX];

void solve(){
    int n = read(), m = read();
    for(int i = 1; i <= n; i++)a[i] = b[i] = deg[i] = deg2[i] = vis[i] = to[i] = fl[i] = 0;
    for(int i = 1; i <= n; i++)g[i].clear(),g2[i].clear();
    for(int i = 1; i <= n; i++){
        a[i] = read();
        if(a[i] == 0)   a[i] = inf;
        else b[i] = a[i], to[a[i]] = i;
    }
    for(int i = 1; i <= m; i++){
        int u = read(), v = read();
        g[u].pb(v);
        g2[v].pb(u);
        deg[v]++;
        deg2[u]++;
    }
    queue <int> que2;
    for(int i = 1; i <= n; i++){
        if(!deg2[i])    que2.push(i);
    }
    while(!que2.empty()){
        int u = que2.front();
        que2.pop();
        for(int v : g2[u]){
            deg2[v]--;
            a[v] = min(a[v], a[u]);
            if(!deg2[v])    que2.push(v);
        }
    }
    // for(int i = 1; i <= n; i++){
        // write(a[i]), put();
    // }endl;

    priority_queue <pair <int, int> > que;

    // write(deg[13]), endl;
    // for(int v : g[13]){
        // write(a[v]), endl;
    // }

    for(int i = 1; i <= n; i++){
        // if(b[i] == 700){
            // write(a[13]), endl;
            // for(int v : g2[i])   write(v), put();
            // endl;
        // }
        if(!deg[i]){

            if(b[i] == a[i]){
                // if(b[i] == 700)  puts("fjk");
                // write(g[i] == 700)   puts("kf");
                fl[b[i]] = 1;
            }else que.push(make_pair(-a[i], i));
        }
    }
    // write(que.top().first), endl;
    for(int i = 1; i <= n; i++){
        if(to[i]){
            if(!fl[i]){
                // write(i), endl;
                puts("-1");

                for(int i = 1; i <= n; i++)a[i] = b[i] = deg[i] = deg2[i] = vis[i] = to[i] = fl[i] = 0;
                for(int i = 1; i <= n; i++)g[i].clear(),g2[i].clear();
                return ;
            }   
            if(!que.empty() and -que.top().first <= i){
                puts("-1");

                for(int i = 1; i <= n; i++)a[i] = b[i] = deg[i] = deg2[i] = vis[i] = to[i] = fl[i] = 0;
                for(int i = 1; i <= n; i++)g[i].clear(),g2[i].clear();
                // write(i), put();
                return ;
            }   
            int u = to[i];
            b[u] = i;
            for(int v : g[u]){
                deg[v]--;
                if(!deg[v]){
                    if(a[v] == b[v]){
                        fl[b[v]] = 1;
                    }else{
                        que.push(make_pair(-a[v], v));
                    }
                }
            }
        }else{
            if(que.empty()) {

                puts("-1");
                for(int i = 1; i <= n; i++)a[i] = b[i] = deg[i] = deg2[i] = vis[i] = to[i] = fl[i] = 0;
                for(int i = 1; i <= n; i++)g[i].clear(),g2[i].clear();
                return ;
            }
            int u = que.top().second;
            b[u] = i;
            que.pop();
            for(int v : g[u]){
                deg[v]--;
                if(!deg[v]){
                    if(a[v] == b[v]){
                        fl[b[v]] = 1;
                    }else{
                        que.push(make_pair(-a[v], v));
                    }
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        write(b[i]), put();
    }
    endl;
}

signed main(){
    // freopen("permutation.in", "r", stdin);
    // freopen("permutation.out", "w", stdout);
    int t = read();
    while(t--)  solve();
    return 0;
}