제출 #372985

#제출 시각아이디문제언어결과실행 시간메모리
372985Matteo_Verz슈퍼트리 잇기 (IOI20_supertrees)C++17
0 / 100
1 ms364 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; int construct(vector<vector<int>> p) { int n = p.size(); vector<vector<int>> answer; answer.resize(n); for(int i = 0; i < n; i++) answer[i].resize(n); vector <int> comp; // last subtask, p[i][j] == 3 for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) if(p[i][j] > 2) return 0; if(p[i][i] != 0) return 0; } vector <bool> isroot; int countcomp(0); comp.resize(n); isroot.resize(n); for(int i = 0; i < n; i++) { // we consider i to be the root of the connected component if(comp[i] != 0) continue; // it can't be a root comp[i] = ++countcomp; isroot[i] = true; for(int j = 0; j < n; j++) { if(i == j) continue; if(p[i][j] == 1) { // if there is only 1 edge from i to j comp[j] = countcomp; answer[i][j] = answer[j][i] = 1; } } } // now we connect the roots between them to form a cycle // we connect the i-th root with the i+1-th root for(int i = 0; i < n; i++) { if(isroot[i] == true) { for(int j = i + 1; j < n; j++) { if(p[i][j] == 2 && isroot[j]) { answer[i][j] = answer[j][i] = 1; j = n; } } } } // we connect the last with the first root for(int i = 0; i < n; i++) { if(isroot[i] == true) { for(int j = n - 1; j > i; j--) { if(p[i][j] == 2 && isroot[j]) { answer[i][j] = answer[j][i] = 1; j = 0; } } i = n; } } // now we need to verify if our build is fine // 1. We can't have a cycle of length 2 if(countcomp == 2) { for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(p[i][j] == 2) return 0; } // 2. If p[a][b] = 1 and p[b][c] = 1, then p[a][c] = 1 for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) if(comp[i] != comp[j] && p[i][j] == 1) 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...