Submission #1241038

#TimeUsernameProblemLanguageResultExecution timeMemory
124103812baaterConnecting Supertrees (IOI20_supertrees)C++20
21 / 100
117 ms22160 KiB
#include "supertrees.h" #include <vector> using namespace std; int find(vector<int>& link, int x) { while (x != link[x]) { x = link[x]; } return x; } void join(vector<int>& link, vector<int>& sz, int a, int b) { a = find(link, a); b = find(link, b); if (sz[a] < sz[b]) swap(a,b); link[b] = a; } bool same(vector<int>& link, int a, int b) { return find(link, a) == find(link,b); } int construct(vector<vector<int>> p) { int n = p.size(); vector<vector<int>> answer(n, vector<int>(n)); vector<int> link(n); vector<int> sz(n, 0); for (int i = 0; i < n; i++) { link[i] = i; } for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { if (p[i][j] && !same(link, i, j)) { join(link, sz, i,j); answer[i][j] = 1; answer[j][i] = 1; } } } for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { if (!p[i][j] && same(link, i, j)) { 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...