QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#332192#8055. Balanceucup-team992WA 254ms3772kbC++146.9kb2024-02-19 11:31:202024-02-19 11:31:20

Judging History

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

  • [2024-02-19 11:31:20]
  • 评测
  • 测评结果：WA
  • 用时：254ms
  • 内存：3772kb
查看
  • [2024-02-19 11:31:20]
  • 提交

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) continue;
            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];
                    if(!look) return true;
                    goto quit;
                }
            }
        }
    }
    

    quit:

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

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

                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;
        }
    }


    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: 3772kb

input:

5
5 4
1 2
2 3
3 4
4 5
1 2 3 4 5
5 4
1 2
1 3
1 4
1 5
1 2 3 4 5
5 4
1 2
1 3
1 4
1 5
1 2 2 2 3
5 6
1 2
1 2
2 3
3 4
4 5
3 5
1 2 1 2 1
2 2
1 2
1 2
1 2

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: 254ms
memory: 3540kb

input:

100000
4 3
4 2
1 3
2 1
2 1 3 2
5 7
2 5
5 3
2 3
5 1
4 3
2 4
4 3
1 3 1 1 2
3 2
2 1
2 3
1 1 1
4 7
3 4
1 4
2 3
4 3
4 2
3 1
4 3
2 3 3 2
4 6
2 4
3 1
1 2
1 2
2 3
4 2
1 1 3 3
4 7
3 2
4 2
1 2
3 4
3 2
2 4
3 4
2 1 1 1
5 5
3 2
1 5
4 5
4 3
2 1
1 2 2 3 2
3 5
2 3
1 3
3 1
3 1
2 1
3 2 3
2 3
2 1
2 1
1 2
1 1
2 3
2 1
1...

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)
English 繁體中文 简体中文

Server Time: 2024-12-02 22:48:32 | OpenSource Project