QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#332154	#8055. Balance	ucup-team992	WA	222ms	3752kb	C++14	7.1kb	2024-02-19 10:50:15	2024-02-19 10:50:15

Judging History

你现在查看的是最新测评结果

[2024-02-19 10:50:15]
评测

测评结果：WA
用时：222ms
内存：3752kb

查看

[2024-02-19 10:50:15]
提交

answer

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define vll vector<long long>

vll val,comp,z,cont;
vll tk;
vector<vll> comps;
ll Time,ncomps;
ll dfs(ll j, vector<vector<pair<ll,ll>>>& g) {
    ll low = val[j] = ++Time,x; z.push_back(j);
    for(auto f: g[j]) {
        if(tk[f.second]) continue;
        tk[f.second]=1;
        auto e=f.first;
        if(comp[e]<0) low=min(low,val[e]?:dfs(e,g));
        tk[f.second]=0;
    }
    if(low==val[j]){
        do{
            x=z.back();z.pop_back();comp[x]=ncomps;
            cont.push_back(x);
        } while(x!=j);

        comps.push_back(cont);
        
        cont.clear();
        ncomps++;
    }
    return val[j]=low;
}

void scc( vector<vector<pair<ll,ll>>>& g, int M) {
    ll n = g.size();
    val.assign(n,0); comp.assign(n,-1);
    tk.assign(M,0); comps = {};
    Time=ncomps=0;
    for(ll i = 0; i < n; i++) if(comp[i]<0)dfs(i,g);
}

vll STS;
void csts(int n, int p, vector<vector<pair<ll,ll>>>& adj) {
    STS[n] += comps[n].size();

    for(auto e: comps[n]) { 
        for(auto aa: adj[e]) {
            ll a = aa.first;
            if(comp[a] != comp[e] && comp[a] != p) {
                csts(comp[a], n, adj);

                STS[n] += STS[comp[a]];
            }
        }
    }
}

vll PCS;
vll SCS;
vll AC, R;
vll pref,suf;

void fill(int n, int p, vector<vector<pair<ll,ll>>>& adj, int c) {
    for(auto e: comps[n]) { 
        if(R[e] != -1) return;
        R[e] = c;
        for(auto aa: adj[e]) {
            ll a = aa.first;
            if(comp[a] != comp[e] && comp[a] != p) {
                fill(comp[a], n, adj, c);
            }
        }
    }
}

bool color(int n, int p, vector<vector<pair<ll,ll>>>& adj, int ip, int is) {
    //std::cout << "color " << comps[n][0] << " " << comps[p][0] << "  " << ip << " " << is << endl; 
    bool look = false;
    int ns = ncomps - ip - 3;
    int np = ncomps - is - 3;

    int npp = -1, nss = -1;

    if(ip >= 0 && pref[ip] == STS[n]) {
        look = true;
        if(ip > 0) npp = PCS[ip-1];
        else {
            PCS[0]++;
            fill(n,p, adj, AC[0]);
            return true;
        }
    }
    
    if(is >= 0 && suf[is] == STS[n]) {
        look = true;
        if(is > 0) nss = SCS[is-1];
        else {
            SCS[0]++;
            fill(n,p, adj, AC[AC.size()-1]);
            return true;
        }
    }

    ll colored = -1;

    for(auto e: comps[n]) { 
        for(auto aa: adj[e]) {
            ll a = aa.first;
            if(R[a] != -1) return false;
            if(comp[a] != comp[e] && comp[a] != p) {
                int ipp = ip;
                int iss = is;
                if(look) {ipp--; iss--;}
                if(color(comp[a], n, adj, ipp, iss)) {
                    colored = comp[a];
                    goto quit;
                }
            }
        }
    }
    

    quit:
    if(!look) return true;

    //std::cout << "color " << n << " " << colored << endl;

    if(ip >= 0 && pref[ip] == STS[n]) {
        if(PCS[ip-1]>npp) {
                PCS[ip]++;

                fill(n,p,adj,AC[ip]);

                

                //cout << "RETURN\n";

                return true;
        }
    }
    
    if(is >= 0 && suf[is] == STS[n]) {
        if(SCS[is-1]>nss) {
                SCS[is]++;

                fill(n,p,adj,AC[AC.size()-1-is]);

                return true;
        }
    }

    //cout << "FAIL\n";

    return false;
}


bool recur(int n, int p, vector<vector<pair<ll,ll>>>& adj, int ip, int is) {
    while(ip >= 0 && pref[ip] > STS[n]) ip--;
    while(is >= 0 && suf[is] > STS[n]) is--;

    //std::cout << "recur" << comps[n][0] << " " << STS[n] << " " << ip << " " << is << endl;
    //std::cout << pref[ip] << " " << suf[is] << endl;

    bool gp = false;
    int ns = AC.size() - ip - 3;
    int np = AC.size() - is - 3;
    bool gs = false;

    int npp = -1, nss = -1;

    if(ip >= 0 && pref[ip] == STS[n]) {
        if(ns < 0 || SCS[ns]>0) gp=true;
        if(ip > 0) npp = PCS[ip-1];
    }
    
    if(is >= 0 && suf[is] == STS[n]) {
        if(np < 0 || SCS[np]>0) gs = true;
        if(is > 0) nss = SCS[is-1];
    }

    for(auto e: comps[n]) { 
        for(auto aa: adj[e]) {
            ll a = aa.first;
            if(comp[a] != comp[e] && comp[a] != p) {
                if(recur(comp[a], n, adj, ip, is)) return true;
            }
        }
    }

    if(ip >= 0 && pref[ip] == STS[n]) {
        if(ip == 0 || PCS[ip-1]>npp) {
            if(gp) {
                //cout << comps[n][0] << "!!!\n";
                //cout << ip << " " << ns << "???\n";
                color(n,p,adj, ip, -1);
                //cout << "TRY 2\n"; 
                color(0,-1,adj,-1,ns);
                //for(int i = 0; i < R.size(); i++)
                //cout << R[i] << (i == R.size()-1 ? "\n": " ");
                
                int left = ip + 1;
                fill(0,-1,adj,AC[left]);

                return true;
            }

            PCS[ip]++;
            //std::cout << "good prefix! " << ns << "\n";
        }
    }
    
    if(is >= 0 && suf[is] == STS[n]) {
        if(is == 0 || SCS[is-1]>nss) {
            if(gs) {
                color(n,p, adj, -1, is);
                color(0,-1,adj, np, -1);
                int left = is+1;
                fill(0,-1,adj,AC[AC.size()-1-left]);

                return true;
            }

            SCS[is]++;
            //std::cout << "good suffix!\n";
        }
    }
    //std::cout << "ret\n";
    return false;
}


int main() {
    ll T; cin >> T;
    for(ll t = 0; t < T; t++) {
        ll N, M; cin >> N >> M;
        vector<vector<pair<ll,ll>>> adj(N);
        for(int i = 0; i < M; i++) {
            int U,V; cin >> U >> V;
            U--; V--;
            adj[U].push_back({V,i});
            adj[V].push_back({U,i});
        }

        vector<ll> A(N);
        for(int i = 0; i < N; i++) cin >> A[i];
        sort(A.begin(), A.end());
        int nd = 0;
        for(int i = 1; i < N; i++) if(A[i] != A[i-1]) nd++;

        AC = {};

        suf = {};
        pref = {};
        int np = 0;
        for(int i = 0; i < N; i++) {
            while(i+1<N && A[i+1]==A[i]) {i++;np++;}
            AC.push_back(A[i]);
            np++;
            pref.push_back(np);
        }

        int ns = 0;

        for(int i = N-1; i >= 0; i--) {
            while(i-1>=0 && A[i-1]==A[i]) {
                i--;ns++;
            }
            ns++;
            suf.push_back(ns);
        }

        scc(adj,M);

        STS.assign(ncomps,0LL);
        csts(0,-1,adj);

        
        PCS.assign(ncomps,0LL);
        SCS.assign(ncomps,0LL);
        R.assign(N,-1LL);
        bool res = recur(0,-1,adj,AC.size()-1,AC.size()-1);

        if(res) {
            cout << "Yes\n";
            for(int i = 0; i < N; i++)
                cout << R[i] << (i == N-1 ? "\n": " ");
        } else {
            cout << "No\n";
        }
    }
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3612kb

input:

output:

Yes
1 2 3 4 5
No
Yes
2 2 3 1 2
Yes
2 2 1 1 1
No

result:

ok ok (5 test cases)

Test #2:

score: -100

Wrong Answer

time: 222ms

memory: 3752kb

input:

output:

Yes
2 2 3 1
No
Yes
1 1 1
No
No
Yes
2 1 1 1
No
No
Yes
1 1
Yes
1 1
Yes
1 1
Yes
1 1 1 1
No
Yes
1 1 1 1 1
Yes
1 3 1 1 1
Yes
1 1 1
Yes
1 2
Yes
1 1 1 1 1
Yes
1 2
No
Yes
1 1
Yes
1 1 1
Yes
1 1
Yes
1 1 1 1
Yes
1 1
Yes
2 2 2 2 2
Yes
1 1 1 1 1
Yes
1 1
Yes
1 2 1 1
No
Yes
1 1
No
Yes
1 1
No
No
No
Yes
2 1 1 1 1
Ye...

result:

wrong answer 1-th smallest numbers are not same (test case 208)