Submission #536681

#TimeUsernameProblemLanguageResultExecution timeMemory
536681MOUF_MAHMALATIzlet (COI19_izlet)C++14
0 / 100
582 ms36128 KiB
#include<bits/stdc++.h> #define all(s) s.begin(),s.end() #define F first #define S second using namespace std; typedef int ll; ll n,t,a[3009][3009],p[3009],sz[3009],c[3009],b[3009],up[3009]; vector<vector<ll> >v; ll gp(ll z) { if(p[z]==z) return z; return p[z]=gp(p[z]); } ll op(ll z) { if(up[z]==z) return z; return up[z]=op(up[z]); } bool mrg(ll x,ll y) { x=gp(x),y=gp(y); if(x==y) return 0; if(sz[x]<sz[y]) swap(x,y); p[y]=x; sz[x]+=sz[y]; return 1; } void dfs(ll d,ll p,ll co,ll x,ll root) { if(b[c[d]]==0) x++; b[c[d]]++; if(a[d][root]>x) { b[c[d]]--; while(b[co]) co++; b[co]++; x++; c[d]=co; } //cout<<d<<" "<<c[d]<<"\n"; for(auto&z:v[d]) if(z!=p) dfs(z,d,co,x,root); b[c[d]]--; } void go(ll d,ll p) { for(auto&z:v[d]) if(z!=p) { cout<<"\n"<<z<<" "<<d; go(z,d); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>t>>n; for(ll i=1; i<=n; i++) for(ll j=1; j<=n; j++) cin>>a[i][j]; for(ll i=1; i<=n; i++) p[i]=i,sz[i]=1; v.resize(n+1); for(ll i=1; i<=n; i++) for(ll j=1; j<=n; j++) if(a[i][j]==1) { mrg(i,j); } for(ll i=1; i<=n; i++) if(p[i]!=i) { v[i].push_back(gp(i)); v[gp(i)].push_back(i); } for(ll i=1; i<=n; i++) c[i]=1,up[i]=p[i]; for(ll i=1; i<=n; i++) for(ll j=1; j<=n; j++) if(a[i][j]==2&&mrg(i,j)) { v[op(i)].push_back(op(j)); v[op(j)].push_back(op(i)); } for(ll i=1; i<=n; i++) { memset(b,0,sizeof b); //cout<<i<<"\n"; dfs(i,0,c[i],0,i); } for(ll i=1; i<=n; i++) cout<<c[i]<<" "; go(1,0); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...