#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 time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
582 ms |
36128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
