Submission #571350

#	Time	Username	Problem	Language	Result	Execution time	Memory
571350		Jasiekstrz	Izlet (COI19_izlet)	C++17	100 / 100	649 ms	74828 KiB

izlet

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=3e3;
int t[N+10][N+10];
int c[N+10];
vector<pair<int,int>> ans;
vector<int> e[N+10];
bool vis[N+10];
bool vistmp[N+10];
int k=0;
int dfs2(int x,int z,int y)
{
	vistmp[x]=true;
	if(t[x][y]==t[x][z])
		return c[x];
	for(auto v:e[x])
	{
		if(!vistmp[v])
		{
			auto tmp=dfs2(v,z,y);
			if(tmp!=0)
				return tmp;
		}
	}
	return 0;
}
void dfs(int x,int y,int n)
{
	vis[x]=true;
	for(int i=1;i<=n;i++)
		vistmp[i]=!vis[i];
	c[x]=dfs2(x,y,x);
	if(c[x]==0)
		c[x]=++k;
	for(int i=1;i<=n;i++)
	{
		if(!vis[i] && t[x][i]==1)
		{
			vis[i]=true;
			ans.emplace_back(i,x);
			c[i]=c[x];
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis[i] && t[x][i]==2)
		{
			ans.emplace_back(i,x);
			e[x].push_back(i);
			e[i].push_back(x);
			dfs(i,x,n);
		}
	}
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			cin>>t[i][j];
	}

	//n=9;
	//for(int i=1;i<=n;i++)
	//{
	//	for(int j=1;j<=n;j++)
	//		cerr<<t[i][j]<<" ";
	//	cerr<<"\n";
	//}

	dfs(1,0,n);
	for(int i=1;i<=n;i++)
		cout<<c[i]<<" ";
	cout<<"\n";
	for(auto [a,b]:ans)
		cout<<a<<" "<<b<<"\n";
	return 0;
}

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