Submission #527807

#TimeUsernameProblemLanguageResultExecution timeMemory
527807Servus2022Connecting Supertrees (IOI20_supertrees)C++14
21 / 100
183 ms26968 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; const int NMAX = 1e3 + 1; int N; int P[NMAX][NMAX]; int head[NMAX]; bool Edge[NMAX][NMAX]; vector < int > G[NMAX]; class DisjointSets { int T[NMAX], Size[NMAX]; private: inline int Find (int X) { if(X == T[X]) return X; return (T[X] = Find(T[X])); } inline void my_swap (int &x, int &y) { x = (x ^ y), y = (x ^ y), x = (x ^ y); return; } public: inline void Initialize (int N) { for(int i = 1; i <= N; ++i) T[i] = i, Size[i] = 1; return; } inline bool Unify (int X, int Y) { X = Find(X), Y = Find(Y); if(X == Y) return 0; if(Size[X] < Size[Y]) my_swap(X, Y); Size[X] += Size[Y], Size[Y] = 0; T[Y] = X; return 1; } inline int Who_is_the_boss (int Node) { return Find(Node); } } DSU; void Build_type_1 () { DSU.Initialize(N); for(int i = 1; i <= N; ++i) for(int j = 1; j <= N; ++j) if(P[i][j] == 1) DSU.Unify(i, j); for(int i = 1; i <= N; ++i) head[i] = DSU.Who_is_the_boss(i); return; } void Build_type_2 () { for(int i = 1; i <= N; ++i) for(int j = 1; j <= N; ++j) if(P[i][j] == 2 && head[i] != head[j]) G[head[i]].push_back(head[j]), G[head[j]].push_back(head[i]), Edge[head[i]][head[j]] = Edge[head[j]][head[i]] = 1; return; } int construct (vector < vector < int > > p) { N = (int)p.size(); for(int i = 0; i < N; ++i) for(int j = 0; j < N; ++j) { P[i + 1][j + 1] = p[i][j]; if(p[i][j] == 3) return 0; } Build_type_1(); for(int i = 1; i <= N; ++i) for(int j = 1; j <= N; ++j) if(P[i][j] == 0 && head[i] == head[j]) return 0; for(int i = 1; i <= N; ++i) if(i != head[i]) Edge[i][head[i]] = Edge[head[i]][i] = 1; Build_type_2(); vector < vector < int > > ans; for(int i = 0; i < N; ++i) { vector < int > _temp; for(int j = 0; j < N; ++j) if(Edge[i + 1][j + 1]) _temp.push_back(1); else _temp.push_back(0); ans.push_back(_temp); } 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...