제출 #1264003

#제출 시각아이디문제언어결과실행 시간메모리
1264003Noname_1900Connecting Supertrees (IOI20_supertrees)C++20
21 / 100
128 ms28416 KiB
#include "supertrees.h" #include<bits/stdc++.h> using namespace std; const int NMAX = 1000; int boss[NMAX]; vector<int> dansComp[NMAX]; vector<int> chemins[3][NMAX]; int findBoss(int noeud) { if(boss[noeud] == noeud) return noeud; return boss[noeud] = findBoss(boss[noeud]); } int _size[NMAX]; bool merge(int a, int b) { a = findBoss(a); b = findBoss(b); if(a == b) return false; if(_size[b] > _size[a]) { swap(a, b); } _size[a] += _size[b]; boss[b] = a; for(int i : dansComp[b]) dansComp[a].push_back(i); return true; } vector<vector<int>> answer; void creer(int a, int b) { answer[a][b] = 1; answer[b][a] = 1; merge(a, b); } 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 construct(vector<vector<int>> p) { int n = p.size(); answer.resize(n, vector<int>(n)); for(int i = 0; i < n; i++) { _size[i] = 1; boss[i] = i; dansComp[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 ++) { 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; } } } /** */ for(int i = 0; i < n; i++) { for(int autre = 0; autre < n; autre++) { if(p[i][autre] == 2) { merge(findBoss(i), findBoss(autre)); } } } // 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(((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...