Submission #571350

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
571350	2022-06-01T21:41:14 Z	Jasiekstrz	Izlet (COI19_izlet)	C++17	100 / 100	649 ms	74828 KB

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.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	457 ms	37128 KB	Output is correct
3	Correct	486 ms	37184 KB	Output is correct
4	Correct	434 ms	36908 KB	Output is correct
5	Correct	453 ms	36940 KB	Output is correct

Subtask #2

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	435 ms	36316 KB	Output is correct
2	Correct	462 ms	53620 KB	Output is correct
3	Correct	649 ms	74016 KB	Output is correct
4	Correct	640 ms	74828 KB	Output is correct
5	Correct	399 ms	53528 KB	Output is correct
6	Correct	472 ms	60536 KB	Output is correct
7	Correct	374 ms	49412 KB	Output is correct

Subtask #3

57.0 / 57.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	457 ms	37128 KB	Output is correct
3	Correct	486 ms	37184 KB	Output is correct
4	Correct	434 ms	36908 KB	Output is correct
5	Correct	453 ms	36940 KB	Output is correct
6	Correct	435 ms	36316 KB	Output is correct
7	Correct	462 ms	53620 KB	Output is correct
8	Correct	649 ms	74016 KB	Output is correct
9	Correct	640 ms	74828 KB	Output is correct
10	Correct	399 ms	53528 KB	Output is correct
11	Correct	472 ms	60536 KB	Output is correct
12	Correct	374 ms	49412 KB	Output is correct
13	Correct	477 ms	54440 KB	Output is correct
14	Correct	632 ms	61412 KB	Output is correct
15	Correct	414 ms	53396 KB	Output is correct
16	Correct	498 ms	57988 KB	Output is correct
17	Correct	574 ms	60032 KB	Output is correct
18	Correct	479 ms	53504 KB	Output is correct
19	Correct	508 ms	53448 KB	Output is correct
20	Correct	436 ms	53632 KB	Output is correct
21	Correct	491 ms	54048 KB	Output is correct
22	Correct	511 ms	53708 KB	Output is correct
23	Correct	455 ms	54220 KB	Output is correct
24	Correct	498 ms	60420 KB	Output is correct
25	Correct	434 ms	53528 KB	Output is correct