Submission #1264565

#TimeUsernameProblemLanguageResultExecution timeMemory
1264565Noname_1900Connecting Supertrees (IOI20_supertrees)C++20
56 / 100
126 ms28444 KiB
#include "supertrees.h" #include<bits/stdc++.h> using namespace std; const int NMAX = 1000; int boss[4][NMAX]; vector<int> dansComp[4][NMAX]; vector<int> chemins[4][NMAX]; int findBoss(int noeud, int iType) { if(boss[iType][noeud] == noeud) return noeud; return boss[iType][noeud] = findBoss(boss[iType][noeud], iType); } int _size[4][NMAX]; bool merge(int a, int b, int iType) { a = findBoss(a, iType); b = findBoss(b, iType); if(a == b) return false; if(_size[iType][b] > _size[iType][a]) { swap(a, b); } _size[iType][a] += _size[iType][b]; boss[iType][b] = a; for(int i : dansComp[iType][b]) dansComp[iType][a].push_back(i); dansComp[iType][b].clear(); return true; } vector<vector<int>> answer; void creer(int a, int b, int iType) { answer[a][b] = 1; answer[b][a] = 1; merge(a, b, iType); } /* bool dansCycle[NMAX]; void parcours(int noeud) { for(int pro : chemins[1][noeud]) { if(findBoss(pro) == findBoss(noeud)) continue; creer(noeud, pro); parcours(pro); } }/** */ int vu[NMAX]; int construct(vector<vector<int>> p) { int n = p.size(); answer.resize(n, vector<int>(n)); for(int i = 0; i < n; i++) { for(int n = 0; n < 4; n++) { _size[n][i] = 1; boss[n][i] = i; dansComp[n][i].push_back(i); } for(int v = 0; v < n; v++) answer[i][v] = 0; } for(int i = 0; i < n; i++) { for(int c = 0; c < n ; c ++) { if(i == c) continue; int type = p[i][c]; chemins[type][i].push_back(c); } } /* for(int i = 0; i < n; i++) { for(int autre = 0; autre < i; autre++) { if(p[i][autre] == 1) { creer(findBoss(i), findBoss(autre)); } } } for(int i = 0; i < n; i++) { for(int autre = 0; autre < i; autre++) { if(p[i][autre] == 0) { if(findBoss(i) == findBoss(autre)) return 0; } } } /** */ //type1 for(int i = 0; i < n; i++) { for(int autre = 0; autre < n; autre++) { if(p[i][autre] != p[autre][i]) return 0; if(i == autre) continue; if(p[i][autre] == 1) { merge(findBoss(i, 1), findBoss(autre, 1), 1); } } } for(int noeud1 = 0; noeud1 < n; noeud1++) { if(findBoss(noeud1, 1) != noeud1) continue; if(dansComp[1][noeud1].size() == 1) continue; for(int autre : dansComp[1][noeud1]) { if(autre == noeud1) continue; creer(noeud1, autre, 1); } } for(int i = 0; i < n; i++) { for(int autre = 0; autre < n; autre++) { if(i == autre) continue; if((findBoss(i, 1) == findBoss(autre, 1)) && (p[i][autre] != 1)) return 0;//Averifier } } //type2 for(int i = 0; i < n; i++) { for(int autre = 0; autre < n; autre++) { if(i == autre) continue; if(p[i][autre] == 2) { merge(findBoss(i, 2), findBoss(autre, 2), 2); } } } for(int noeud2 = 0; noeud2 < n; noeud2++) { if(findBoss(noeud2, 2) != noeud2) continue; if(dansComp[2][noeud2].size() == 1) continue; if(dansComp[2][noeud2].size() == 2) return 0; int b = dansComp[2][noeud2][dansComp[2][noeud2].size()-1]; b = findBoss(b, 1); vu[b] = 2; int nbApp = 0; for(int iDansComp=0; iDansComp < dansComp[2][noeud2].size(); iDansComp++) { int a = dansComp[2][noeud2][iDansComp]; a= findBoss(a, 1); if((vu[a] == 2) && (iDansComp != dansComp[2][noeud2].size()-1)) continue; vu[a] = 2; nbApp++; creer(a, b, 2); b = a; } if(nbApp < 2) return 0; } /* for(int i = 0; i < n; i++) { for(int autre = 0; autre < n; autre++) { if(i == autre) continue; if((findBoss(i, 2) == findBoss(autre, 2)) && (p[i][autre] != 2)) return 0; } } /** */ // cout << "passe" << endl; /** for(int i = 0; i < n; i++) { for(int autre = 0; autre < n; autre++) { //cout << i << " " << autre << endl; if(i == autre) continue; if(p[i][autre] == 0) { if(findBoss(i) == findBoss(autre)) return 0; } } } //cout << "passe" << endl; /** */ /* // cycle de 2 for(int i = 0; i < n; i++) { if(findBoss(i) == i) { if(dansComp[i].size() == 1) continue; //if(dansComp[i].size() == 2) return 0; // cout << endl; for(int iDansComp=0; iDansComp < dansComp[i].size(); iDansComp++) { //cout << dansComp[i][iDansComp] << " "; int b; if(iDansComp == 0) { b = dansComp[i][dansComp[i].size()-1]; } else b = dansComp[i][iDansComp-1]; int a = dansComp[i][iDansComp]; dansCycle[a] = true; creer(a, b); } } } // parcours pour arbre depuis cycle for(int i = 0; i < n; i++) { if(!dansCycle[i]) continue; parcours(i); } //reste for(int i = 0; i < n; i++) parcours(i); for(int i = 0; i < n; i++) { for(int autre = 0; autre < n; autre++) { if(i == autre) continue; if(((p[i][autre] == 0) && (findBoss(i) == findBoss(autre))) || ((p[i][autre] > 0) && (findBoss(i) != findBoss(autre)))) return 0; } } /** */ build(answer); return 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...