제출 #1063261

#제출 시각아이디문제언어결과실행 시간메모리
1063261weajinkConnecting Supertrees (IOI20_supertrees)C++17
100 / 100
161 ms24188 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxN = 1001; int par[maxN][2]; int ssize[maxN][2]; int FIND(int x, bool ktory){ if (par[x][ktory] == x) return x; return par[x][ktory] = FIND(par[x][ktory],ktory); } void UNION(int x, int y,bool ktory){ int a = FIND(x,ktory); int b = FIND(y,ktory); if (a == b) return; if (ssize[a][ktory] > ssize[b][ktory]) swap(a,b); par[a][ktory] = b; ssize[b][ktory] += ssize[a][ktory]; } vector<int> cykl[maxN]; int construct(vector<vector<int> > p){ int n = p.size(); int i; for (i = 0; i < n; i++){ par[i][0] = par[i][1] = i; ssize[i][0] = ssize[i][1] = 1; } for (i = 0; i < n; i++){ for (int j = 0; j < n-1; j++){ if (p[i][j] == 3){ return 0; } if (p[i][j]){ UNION(i,j,0); } if (p[i][j] == 1){ UNION(i,j,1); } } } for (i = 0; i < n; i++){ for (int j = 0; j < n; j++){ if (i == j) continue; if (!p[i][j] && FIND(i,0) == FIND(j,0)){ return 0; } if (p[i][j] == 1 && FIND(i,1) != FIND(j,1)){ return 0; } } } vector<vector<int> > wy; wy.resize(n); for (i = 0; i < n; i++){ wy[i].assign(n,0); } for (i = 0; i < n; i++){ if (FIND(i,1) != i){ wy[i][FIND(i,1)] = 1; wy[FIND(i,1)][i] = 1; }else{ cykl[FIND(i,0)].push_back(i); } } for (i = 0; i < n; i++){ if (FIND(i,0) != i) continue; if (cykl[i].size() == 2) return 0; if (cykl[i].size() == 1) continue; for (int j = 0; j < (int)cykl[i].size(); j++){ wy[cykl[i][j]][cykl[i][(j+1)%cykl[i].size()]] = 1; wy[cykl[i][(j+1)%cykl[i].size()]][cykl[i][j]] = 1; } } build(wy); 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...