Submission #1087739

#TimeUsernameProblemLanguageResultExecution timeMemory
1087739T0p_Connecting Supertrees (IOI20_supertrees)C++14
56 / 100
135 ms24184 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; const int N = 1000; bool is_add[N]; int tree_parent[N], circular_parent[N]; int find_tree_parent(int u) { return tree_parent[u] = (u == tree_parent[u]) ? u : find_tree_parent(tree_parent[u]); } int find_circular_parent(int u) { return circular_parent[u] = (u == circular_parent[u]) ? u : find_circular_parent(circular_parent[u]); } int construct(vector<vector<int>> p) { int n = p.size(); vector<vector<int>> ans(n, vector<int>(n)); for (int i=0 ; i<n ; i++) { for (int j=0 ; j<n ; j++) { if (p[i][j] == 3) { return 0; } } } for (int i=0 ; i<n ; i++) { tree_parent[i] = i; circular_parent[i] = i; } for (int i=0 ; i<n ; i++) { for (int j=i+1 ; j<n ; j++) { if (p[i][j] == 1) { int ii = find_tree_parent(i); int jj = find_tree_parent(j); if (ii != jj) { tree_parent[ii] = jj; ans[i][j] = ans[j][i] = 1; } } } } for (int i=0 ; i<n ; i++) { for (int j=i+1 ; j<n ; j++) { int ii = find_tree_parent(i); int jj = find_tree_parent(j); if (p[i][j] != 1 && ii == jj) { return 0; } } } for (int i=0 ; i<n ; i++) { for (int j=i+1 ; j<n ; j++) { if (p[i][j] == 2) { int ii = find_circular_parent(find_tree_parent(i)); int jj = find_circular_parent(find_tree_parent(j)); circular_parent[ii] = jj; } } } vector<int> group[N]; for (int i=0 ; i<n ; i++) { int tree_i = find_tree_parent(i); if (is_add[tree_i]) continue; is_add[tree_i] = true; int circular_i = find_circular_parent(tree_i); group[circular_i].push_back(tree_i); } for (int i=0 ; i<N ; i++) { int sz = group[i].size(); if (sz <= 1) { continue; } else if (sz == 2) { return 0; } else { for (int j=0 ; j<sz-1 ; j++) { ans[group[i][j]][group[i][j+1]] = ans[group[i][j+1]][group[i][j]] = 1; } ans[group[i][0]][group[i][sz-1]] = ans[group[i][sz-1]][group[i][0]] = 1; } } build(ans); 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...