Submission #300457

#TimeUsernameProblemLanguageResultExecution timeMemory
300457mohammadConnecting Supertrees (IOI20_supertrees)C++14
0 / 100
1 ms512 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; typedef long long ll ; int root[1020] , de[1020] , use[1020] , r[1020]; ll find(int u){ if(root[u] == u) return u; return root[u] = find(root[u]); } int construct(vector<vector<int>> p) { int n = p.size(); vector<vector<int>> answer(n , vector<int>(n , 0)); for(int i = 0 ; i < n ; ++i){ if(p[i][i] != 1) return 0 ; root[i] = i ; } for(int i = 0 ; i < n; ++i) for(int j = 0 ; j < n; ++j){ if(!p[i][j]) continue ; if(p[i][j] == 2 || p[i][j] == 0) r[i]++ ; root[find(i)] = find(j); } for(int i = 0 ; i < n ; ++i) { if(r[i] == n - 1) de[i] = 1; else de[i] = 0 ; find(i); } set<int> s[1020][3]; for(int i = 0 ; i < n; ++i) for(int j = i + 1 ; j < n; ++j){ if(p[i][j] == 0 && root[i] == root[j]) return 0 ; else if(p[i][j]){ s[root[i]][de[i]].insert(i); s[root[i]][de[j]].insert(j); } } for(int i = 0 ; i < n; ++i){ if(use[root[i]]) continue; use[root[i]] = 1; int ls = -1; if(!s[root[i]][1].size()){ return 0 ; for(auto j : s[root[i]][0]){ if(ls != -1){ answer[ls][j] = 1;answer[j][ls] = 1; }else ls = j ; } }else if(!s[root[i]][0].size()){ if(s[root[i]][1].size() <= 2) return 0; auto it = s[root[i]][1].begin(); auto it1 = s[root[i]][1].begin(); it1++; auto it2 = s[root[i]][1].begin(); it2++;it2++; answer[*it][*it1] = 1;answer[*it1][*it] = 1; for(; it2 != s[root[i]][1].end(); it2++ , it1++){ answer[*it2][*it1] = 1;answer[*it1][*it2] = 1; } answer[*it][*it1] = 1;answer[*it1][*it] = 1; }else{ return 0 ; if(s[root[i]][1].size() <= 1) return 0; for(auto j : s[root[i]][0]){ if(ls != -1){ answer[ls][j] = 1;answer[j][ls] = 1; }else ls = j ; } int it = ls; auto it1 = s[root[i]][1].begin(); auto it2 = s[root[i]][1].begin(); it2++; answer[it][*it1] = 1;answer[*it1][it] = 1; for(; it2 != s[root[i]][1].end(); it2++ , it1++){ answer[*it2][*it1] = 1;answer[*it1][*it2] = 1; } answer[it][*it1] = 1;answer[*it1][it] = 1; } } 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...