Submission #1081484

#TimeUsernameProblemLanguageResultExecution timeMemory
10814847modyConnecting Supertrees (IOI20_supertrees)C++17
0 / 100
1 ms432 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; int construct(vector<vector<int>> p) { int n = p.size(); vector<vector<int>> ans; for (int i = 0; i < n; i++) { vector<int> row; row.resize(n); ans.push_back(row); } for(int i = 0; i < n;i++){ if(p[i][i] != 1) return 0; for(int j = i + 1;j < n;j++){ if(p[i][j] != p[j][i] || p[i][j] == 3) return 0; } } vector<bool> vis(n, false); for(int i = 0; i < n;i++){ if(vis[i]) continue; vis[i] = true; vector<int> curr(1, i); for(int j = i + 1; j < n;j++){ if(p[i][j] != 0 && vis[j]) return 0; if(p[i][j] != 0) curr.push_back(j), vis[j] = true; } int m = curr.size(); vector<vector<int>> branches; vector<bool> temp(n, false); for(int a = 0; a < m;a++){ int x = curr[a]; if(temp[x]) continue; vector<int> add; add.push_back(x); for(int b = a+1; b < m;b++){ int y = curr[b]; if(p[x][y] == 1){ add.push_back(y); temp[y] = true; } } branches.push_back(add); } for(vector<int> x : branches){ for(int a : x){ for(int b : x){ if(a == b) continue; if(p[a][b] != 1) return 0; ans[a][b] = 1; } } } int szbr = branches.size(); int szcurr = curr.size(); for(int x = 0; x < szbr;x++){ vector<bool> bb(n); for(int a : branches[x]){ bb[a] = true; } for(int a : branches[x]){ for(int b : curr){ if(bb[b]) continue; if(p[a][b] != 2) return 0; } } } for(int j = 1; j < szcurr;j++){ for(int k = 0; k < n;k++){ int a = curr[j]; int b = curr[0]; if(a == k || b == k) continue; bool ok1 = p[a][k] >=1; bool ok2 = p[b][k] >=1; if(ok1 != ok2) return 0; } } for(int x = 0; x < szbr - 1; x++){ ans[branches[x][0]][branches[x+1][0]] = ans[branches[x+1][0]][branches[x][0]] = 1; } if(branches.size() > 1) ans[branches[0][0]][branches[szbr-1][0]] = ans[branches[szbr-1][0]][branches[0][0]] = 1; } build(ans); // for(auto x : ans){ // for(auto y : x){ // cout << y << ' '; // } cout << '\n'; // } return 1; } // int32_t main(){ // // cout << construct({{1, 1, 2, 2}, {1, 1, 2, 2}, {2, 2, 1, 2}, {2, 2, 2, 1}}) << '\n'; // cout << construct({{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...