oj.uz

답안 #1041443

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1041443 2024-08-02T04:02:06 Z vjudge1 Izlet (COI19_izlet) C++17
25 / 100
 540 ms 497600 KB 
#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] and dist[j][i]==dist[j][i-1])
			{
				found=1;
				color[i]=color[j];
			}
		}
		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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 473 ms 461568 KB Output is correct
2 Correct 466 ms 478352 KB Output is correct
3 Correct 528 ms 496764 KB Output is correct
4 Correct 540 ms 497600 KB Output is correct
5 Correct 432 ms 478332 KB Output is correct
6 Correct 465 ms 484744 KB Output is correct
7 Correct 299 ms 249996 KB Output is correct

Subtask #3
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -