oj.uz

Submission #571345

# Submission time Handle Problem Language Result Execution time Memory
571345 2022-06-01T21:06:10 Z Jasiekstrz Izlet (COI19_izlet) C++17
18 / 100
 501 ms 53848 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 lst,int y)
{
	vistmp[x]=true;
	if(t[x][y]==lst)
		return c[x];
	for(auto v:e[x])
	{
		if(!vistmp[v])
		{
			auto tmp=dfs2(v,lst+1,y);
			if(tmp!=0)
				return tmp;
		}
	}
	return 0;
}
void dfs(int x,int n)
{
	vis[x]=true;
	for(int i=1;i<=n;i++)
		vistmp[i]=!vis[i];
	c[x]=dfs2(x,0,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,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];
	}
	dfs(1,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 446 ms 53848 KB Output is correct
3 Correct 501 ms 53700 KB Output is correct
4 Correct 417 ms 53440 KB Output is correct
5 Correct 434 ms 53552 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 470 ms 37196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 446 ms 53848 KB Output is correct
3 Correct 501 ms 53700 KB Output is correct
4 Correct 417 ms 53440 KB Output is correct
5 Correct 434 ms 53552 KB Output is correct
6 Incorrect 470 ms 37196 KB Output isn't correct
7 Halted 0 ms 0 KB -