Submission #548682

#TimeUsernameProblemLanguageResultExecution timeMemory
548682Clan328Connecting Supertrees (IOI20_supertrees)C++17
21 / 100
221 ms23984 KiB
#include "supertrees.h" #include <vector> #include <bits/stdc++.h> using namespace std; vector<int> link; int find(int x) { if (link[x] != x) link[x] = find(link[x]); return link[x]; } void unite(int a, int b) { int x = find(a), y = find(b); link[x] = y; } bool same(int a, int b) { return find(a) == find(b); } int construct(vector<vector<int>> p) { int n = p.size(); vector<vector<int>> answer(n, vector<int>(n)); link = vector<int>(n); iota(link.begin(), link.end(), 0); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) continue; if (p[i][j]) unite(i, j); } } for (int i = 0; i < n; i++) { int par = find(i); if (i != par) { answer[i][par] = 1; answer[par][i] = 1; } } bool res = true; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) continue; res &= ((bool)p[i][j] == same(i, j)); } } if (res) { build(answer); return 1; } else return 0; }
#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...