제출 #336812

#제출 시각아이디문제언어결과실행 시간메모리
336812MvC슈퍼트리 잇기 (IOI20_supertrees)C++17
0 / 100
1 ms620 KiB
#include "supertrees.h" #include <bits/stdc++.h> #define rc(x) return cout<<x<<endl,0 #define pb push_back #define mkp make_pair #define in insert #define er erase #define fd find #define fr first #define sc second #define all(x) x.begin(),x.end() #define lun(x) (int)x.size() typedef long long ll; typedef long double ld; const ll INF=0x3f3f3f3f3f3f3f3f; const ll llinf=(1LL<<60); const int inf=(1<<30); const int nmax=1e3+50; const ll mod=1e9+7; using namespace std; int n,i,j,t,p1[nmax],p2[nmax]; vector<vector<int> >b; vector<int>v1[nmax],v2[nmax],vc; int fnd1(int x) { if(p1[x]==x)return x; return p1[x]=fnd1(p1[x]); } void uni1(int x,int y) { x=fnd1(x),y=fnd1(y); if(x==y)return; p1[x]=y; } int fnd2(int x) { if(p2[x]==x)return x; return p2[x]=fnd2(p2[x]); } void uni2(int x,int y) { x=fnd2(x),y=fnd2(y); if(x==y)return; p2[x]=y; } int construct(vector<vector<int> > r) { n=lun(r); for(i=0;i<n;i++)for(j=0;j<n;j++)if(r[i][j]==3)return 0; for(i=0;i<n;i++)p1[i]=p2[i]=i; for(i=0;i<n;i++)for(j=0;j<n;j++)if(r[i][j])uni1(i,j); for(i=0;i<n;i++)for(j=0;j<n;j++)if(!r[i][j] && fnd1(i)==fnd1(j))return 0; for(i=0;i<n;i++)for(j=0;j<n;j++)if(r[i][j]==1)uni2(i,j); for(i=0;i<n;i++)for(j=0;j<n;j++)if(r[i][j]!=1 && fnd2(i)==fnd2(j))return 0; for(i=0;i<n;i++)v1[fnd1(i)].pb(i); for(i=0;i<n;i++)b[i].resize(n); for(i=0;i<n;i++) { if(v1[i].empty())continue; for(j=0;j<lun(v1[i]);j++)v2[fnd2(v1[i][j])].pb(v1[i][j]); vc.clear(); for(j=0;j<n;j++) { if(v2[j].empty())continue; for(t=0;t<lun(v2[j])-1;t++) { b[v2[j][t]][v2[j][t+1]]=b[v2[j][t+1]][v2[j][t]]=1; } vc.pb(j); v2[j].clear(); } if(lun(vc)==2)return 0; for(j=0;j<lun(vc)-1;j++)b[vc[j]][vc[j+1]]=b[vc[j+1]][vc[j]]=1; } build(b); return 1; } /*int main() { //freopen("sol.in","r",stdin); //freopen("sol.out","w",stdout); //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0); return 0; }*/
#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...