QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#339324#8055. BalanceSTnofarjoWA 138ms11708kbC++207.5kb2024-02-27 02:30:282024-02-27 02:30:29

Judging History

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

  • [2024-02-27 02:30:29]
  • 评测
  • 测评结果：WA
  • 用时：138ms
  • 内存：11708kb
查看
  • [2024-02-27 02:30:28]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define pll pair<long long, long long>

const int maxn = 300300;
bool vis[maxn];
int t, n, m, u, v;
map<pii, int> freqEdge;
int nodeComp[maxn], nbcomp, times[maxn][2], timer; // tin, low
vector<int> al[maxn], compNodes[maxn], child[maxn];
int compPar[maxn];

void dfsComp(int node, int par){
    nodeComp[node] = nbcomp;
    compNodes[nbcomp].push_back(node);
    //cout << "masukin " << node << " ke " << nbcomp << endl;
    for(int i=0; i<al[node].size(); i++){
        int to = al[node][i];
        if(to != par){
            if(nodeComp[to] == 0){
                dfsComp(to, node);
            }else if(nodeComp[to] != nbcomp){
                child[nbcomp].push_back(nodeComp[to]);
                compPar[nodeComp[to]] = nbcomp;
            }
        }
    }
}
void dfsBridge(int node, int par){
    vis[node] = true;
    times[node][0] = timer; // tin
    times[node][1] = timer; // low
    timer++;
    for(int i=0; i<al[node].size(); i++){
        int to = al[node][i];
        if(to == par) continue;
        if(vis[to]){ // back edge
            times[node][1] = min(times[node][1], times[to][0]);
        }else{
            dfsBridge(to, node); 
            times[node][1] = min(times[node][1], times[to][1]);
            if(times[to][1] > times[node][0] && freqEdge[{min(node,to),max(node,to)}] == 1){
                // node-to bridge
                //cout << "nemu bridge " << node << "-" << to << endl;
                nbcomp++; dfsComp(to, node);
            }
        }
    }
}

int vals[maxn], info[maxn][3]; //0,1,2 = subtree, nunjuk kiri, kanan (-1 klo gbs, 0 klo leaf)
int ans[maxn];
vector<int> uvals, nodes;
void dfsAns(int node, int val){
    //cout << "warnain comp " << node << " pake " << val << endl;
    for(int i=0; i<compNodes[node].size(); i++){
        ans[compNodes[node][i]] = val;
    }
    for(int i=0; i<child[node].size(); i++){
        int to = child[node][i];
        //cout << node << " punya anak " << to << endl;
        if(ans[compNodes[to][0]] == 0){
            dfsAns(to, val);
        }
    }
}
bool dfsTree(int node){
    //cout << "visit " << node << " with par " << compPar[node] << endl;
    info[node][0] = compNodes[node].size();
    for(int i=0; i<child[node].size(); i++){
        //cout << node << " punya anak " << child[node][i] << endl;
        if(dfsTree(child[node][i])){
            return true;
        }else{
            info[node][0] += info[child[node][i]][0];
        }
    }
    info[node][1] = -1; info[node][2] = -1;
    if(vals[info[node][0]-1] == 1) info[node][1] = 0;
    if(vals[n-info[node][0]] == uvals.size()) info[node][2] = 0;
    
    vector<pii> kirivals, kananvals;
    kirivals.push_back({1, 0});
    kananvals.push_back({uvals.size(), 0});
    // ngitung nunjuk
    for(int i=0; i<child[node].size(); i++){
        int to = child[node][i];
        if(vals[info[to][0]-1] != vals[info[to][0]]){ // kiri bisa nunjuk persis ke to
            if(info[node][1]<0 || info[to][0] > info[info[node][1]][0]){
                info[node][1] = to;
            } 
            kirivals.push_back({vals[info[to][0]], to});
        }
        if(info[to][1] >= 0){ // kiri bisa nunjuk ditunjuk to
            int kirito = info[to][1];
            if(info[node][1]<0 || info[kirito][0] > info[info[node][1]][0]){
                info[node][1] = kirito;
            }
            kirivals.push_back({vals[info[kirito][0]], -to});
        }
        if(vals[n-info[to][0]] != vals[n-1-info[to][0]]){ // kanan bisa nunjuk persis ke to
            if(info[node][2]<0 || info[to][0] > info[info[node][2]][0]){
                info[node][2] = to;
            }
            kananvals.push_back({vals[n-1-info[to][0]], to});
        }
        if(info[to][2] >= 0){ // kanan bisa nunjuk ditunjuk to
            int kananto = info[to][2];
            if(info[node][2]<0 || info[kananto][0] > info[info[node][2]][0]){
                info[node][2] = kananto;
            }
            kananvals.push_back({vals[n-1-info[kananto][0]], -to});
        }
    }
    // cek apakah bisa lgsg kelar
    sort(kirivals.begin(), kirivals.end());
    sort(kananvals.begin(), kananvals.end());
    int ikiri = 0, ikanan = 0;
    while(ikiri<kirivals.size() && ikanan<kananvals.size()){
        if(kirivals[ikiri].first < kananvals[ikanan].first){
            ikiri++;
        }else if(kirivals[ikiri].first > kananvals[ikanan].first){
            ikanan++;
        }else if(abs(kirivals[ikiri].second) != abs(kananvals[ikanan].second) || n==1){ // dapet jawaban
            nodes.clear(); // kiri
            int cur = kirivals[ikiri].second; 
            if(cur < 0) cur = info[-kirivals[ikiri].second][1];
            while(cur!=0){
                nodes.push_back(cur); cur = info[cur][1];
            }
            for(int i=0; i<nodes.size(); i++){
                dfsAns(nodes[nodes.size()-1-i], uvals[i]);
                //cout << "kelar warnain " << nodes[nodes.size()-1-i] << " pake " << uvals[i] << endl;
            }
            nodes.clear(); // kanan
            cur = kananvals[ikanan].second;
            if(cur < 0) cur = info[-kananvals[ikanan].second][2];
            while(cur!=0){
                nodes.push_back(cur); cur = info[cur][2];
            }
            for(int i=0; i<nodes.size(); i++){
                dfsAns(nodes[nodes.size()-1-i], uvals[uvals.size()-1-i]);
                //cout << "kelar warnain " << nodes[nodes.size()-1-i] << " pake " << uvals[uvals.size()-1-i] << endl;
            }
            dfsAns(nbcomp, uvals[kirivals[ikiri].first-1]);
            //cout << "kelar warnain " << nbcomp << " pake " << uvals[kirivals[ikiri].first-1] << endl;
            return true;
        }else if(ikiri<kirivals.size()-1 && kirivals[ikiri+1].first == kirivals[ikiri].first){
            ikiri++;
        }else if(ikanan<kananvals.size()-1 && kananvals[ikanan+1].first == kananvals[ikanan].first){
            ikanan++;
        }else{
            ikiri++; ikanan++;
        }
    }
    // reset 
    return false;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> t;
    while(t--){
        cin >> n >> m; freqEdge.clear();
        while(m--){
            cin >> u >> v; //u++; v++;
            al[u].push_back(v); al[v].push_back(u);
            freqEdge[{min(u,v), max(u,v)}]++;
        }
        timer = 0; nbcomp = 0;
        dfsBridge(1, 0);
        nbcomp++; dfsComp(1, 0);
        
        // urus val
        uvals.clear();
        for(int i=0; i<n; i++){
            cin >> vals[i];
        }
        sort(vals, vals+n);
        for(int i=0; i<n; i++){
            if(uvals.size()==0 || vals[i] != uvals[uvals.size()-1]){
                uvals.push_back(vals[i]);
            }
            vals[i] = uvals.size();
        }
        /*cout << "uvals";
        for(int i=0; i<uvals.size(); i++){
            cout << " " << uvals[i];
        } cout << endl;*/
        //cout << "mau dfs tree" << endl;

        info[0][0] = 0;
        if(dfsTree(nbcomp)){
            cout << "Yes" << endl;
            for(int i=1; i<=n; i++){
                cout << ans[i] << ' ';
            } cout << endl;
        }else{
            cout << "No" << endl;
        }

        //reset
        for(int i=1; i<=n; i++){
            vis[i] = false; 
            nodeComp[i] = 0; ans[i] = 0; 
            al[i].clear(); compNodes[i].clear(); child[i].clear();
        }
    }
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 11708kb

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 3 1 2 2 
Yes
2 2 1 1 1 
No

result:

ok ok (5 test cases)

Test #2:

score: -100
Wrong Answer
time: 138ms
memory: 9780kb

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 1 3 
Yes
3 2 2 2 2 
Yes
1 1 1 
No
No
Yes
2 1 1 1 
No
No
No
No
No
No
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
No
Yes
1 1 1 
Yes
1 1 
No
No
Yes
2 2 2 2 2 
No
Yes
1 1 
Yes
1 1 1 2 
No
No
No
Yes
1 1 
No
No
No
Yes
1 1 1 1 2 
Yes
1 2 1 1 
No
No
No
No
Yes
3 1 ...

result:

wrong answer 1-th smallest numbers are not same (test case 2)
English 繁體中文 简体中文

Server Time: 2024-12-02 16:54:55 | OpenSource Project