Submission #1118711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118711		vjudge1	Izlet (COI19_izlet)	C++17	100 / 100	511 ms	68908 KiB

izlet

#include<bits/stdc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=3005;
int id,n,a[N][N],fa[N],c[N];bool vis[N][N],v[N];
basic_string<int>g[N];vector<pair<int,int>>ans;
inline void add(int u,int v){g[u]+=v,g[v]+=u;ans.push_back({u,v});}
inline int getf(int x){return fa[x]==x?x:fa[x]=getf(fa[x]);}
inline void hb(int x,int y){x=getf(x),y=getf(y);if(x^y) fa[y]=x,add(x,y);}
int m,col,rt;
void dfs1(int x,int fa,int s)
{
	if(col==-1&&a[rt][x]==a[s][x]) col=c[x];
	for(int i:g[x]) if(v[i]&&i!=fa) dfs1(i,x,s);
}
inline void get(int x)
{
	rt=x;col=-1;
	for(int i:g[x]) if(v[i]) dfs1(i,0,i);
	c[x]=(col==-1?++m:col);
}
void dfs(int x)
{
	v[x]=1;get(x);
	for(int i:g[x]) if(!v[i]) dfs(i);
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>id>>n;
	iota(fa+1,fa+1+n,1);
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
		cin>>a[i][j],(a[i][j]==1)&&(hb(i,j),1);
	basic_string<int>rt;
	for(int i=1;i<=n;i++) if(fa[i]==i) rt+=i;
	int m=rt.size();
	for(int i=0;i<m;i++) for(int j=i+1;j<m;j++)
	{
		int u=rt[i],v=rt[j];
		if(a[u][v]==2&&!vis[u][v])
		{
			basic_string<int>h{u,v};
			for(int k=j+1;k<m;k++)
			{
				int w=rt[k];
				if(a[u][w]==2&&a[v][w]==2) h+=w;
			}
			for(int k:h){for(int l:h) vis[k][l]=1;if(k!=h[0]) add(h[0],k);}
		}
	}
	dfs(1);for(int i=1;i<=n;i++) cout<<c[i]<<" ";cout<<"\n";
	for(auto [u,v]:ans) cout<<u<<" "<<v<<"\n";
	return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 25 / 25
• Subtask 3: 57 / 57