oj.uz

답안 #571350

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
571350 2022-06-01T21:41:14 Z Jasiekstrz Izlet (COI19_izlet) C++17
100 / 100
 649 ms 74828 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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