Submission #1041434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041434		vjudge1	Izlet (COI19_izlet)	C++17	0 / 100	513 ms	461712 KiB

izlet

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N=3011;
ll dist[N][N],dist1[N][N],par[N],color[N];
vector<ll> ma[N];
bool vis[N];
// sll added;

int get(int x)
{
	if(par[x]==x)return x;
	return par[x]=get(par[x]);
}
bool merge(int x,int y)
{
	x=get(x),y=get(y);
	if(x==y)return 0;
	par[x]=y;
	return 1;
}
void dfs_(int x,int p=-1,int s=-1)
{
	for(auto y:ma[x])
	{
		if(y==p)continue;
		dist[s][y]=dist[s][x]+1;
		dfs_(y,x,s);
	}
}
void dfs(int x,int p=-1,int s=-1)
{
}
void solve()
{
	ll subtask;
	cin>>subtask;
	ll n;
	cin>>n;
	std::vector<pair<ll,pair<ll,ll>>> v;
	for(int i=1;i<=n;i++)
	{		
		par[i]=i;
		for(int j=1;j<=n;j++)
		{
			cin>>dist[i][j];
			v.push_back({dist[i][j],{i,j}});
		}
	}
	for(int i=1;i<n;i++)
		ma[i].push_back(i+1);
	color[1]=1;
	ll npp=2;
	for(int i=2;i<=n;i++)
	{
		bool found=0;
		for(int j=1;j<i;j++)
		{
			if((dist[j][i])==dist[j+1][i])
			{
				found=1;
				color[i]=color[j];
				break;
			}
		}
		if(!found)
		{
			color[i]=npp;
			npp++;
		}
	}
	for(int i=1;i<=n;i++)
	{
		cout<<color[i]<<' ';
	}
	cout<<endl;
	for(int i=1;i<n;i++)
	{
		cout<<i<<' '<<i+1<<endl;
	}
}

int main()
{
	cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(0);
	int t=1;
	while(t--)
		solve();
}

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