제출 #301580

#제출 시각아이디문제언어결과실행 시간메모리
301580Batyr슈퍼트리 잇기 (IOI20_supertrees)C++17
100 / 100
285 ms26236 KiB
#include <bits/stdc++.h> #include "supertrees.h" using namespace std; #define ll long long #define pii pair<int,int> #define ff first #define ss second #define sz(a) (int)a.size() #define pb push_back const int maxn=1e3+5; // head int n; int d[maxn]; int b[maxn]; vector<vector<int>> p; vector<vector<int>> ans; int ata(int x){ if(x==d[x]) return x; return d[x]=ata(d[x]); } int ata2(int x){ if(x==b[x]) return x; return b[x]=ata2(b[x]); } int f(vector<int>v){ if(sz(v)==0) return 1; for(int i = 0;i < sz(v);i++) b[v[i]]=v[i]; for(int i = 0;i < sz(v);i++){ for(int j = 0;j < i;j++){ if(p[v[i]][v[j]]==1){ int x=ata2(v[i]),y=ata2(v[j]); if(x != y) b[y]=x; } } } vector<int> br[n+1]; set<int> s; for(int i = 0;i < sz(v);i++){ ata2(v[i]); br[b[v[i]]].pb(v[i]); s.insert(b[v[i]]); } for(int i = 0;i < n;i++){ for(int j = 0;j < sz(br[i]);j++){ for(int k = 0;k < j;k++){ if(p[br[i][j]][br[i][k]]==2) return 0; } if(j > 0) ans[br[i][j]][br[i][j-1]]=1,ans[br[i][j-1]][br[i][j]]=1; } } if(sz(s)==2) return 0; if(sz(s)==1) return 1; int fi=-1,ls=-1; for(auto i : s){ if(fi==-1) fi=i; if(ls != -1) ans[i][ls]=1,ans[ls][i]=1; ls=i; } ans[ls][fi]=1,ans[fi][ls]=1; return 1; } int construct(vector<vector<int>> _p) { p = _p; n = p.size(); ans.resize(n); for(int i = 0;i < n;i++){ d[i]=i; ans[i].resize(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++){ for(int j = 0;j < i;j++){ if(p[i][j]>0){ int x=ata(i),y=ata(j); if(x != y) d[y]=x; } } } vector<int>v[n+1]; for(int i = 0;i < n;i++){ ata(i); v[d[i]].pb(i); } for(int i = 0;i < n;i++){ for(int j = 0;j < sz(v[i]);j++){ for(int k = 0;k < j;k++){ if(p[v[i][j]][v[i][k]] == 0) return 0; } } } for(int i = 0;i < n;i++){ int jog = f(v[i]); if(jog==0) return 0; } 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...