Submission #239468

#	Time	Username	Problem	Language	Result	Execution time	Memory
239468		kshitij_sodani	Izlet (COI19_izlet)	C++17	100 / 100	856 ms	61816 KiB

izlet

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
int dist[3001][3001];
int par[3001];
int col[3001];
int find(int no){
	if(par[no]==no){
		return no;
	}
	par[no]=find(par[no]);
	return par[no];
}
vector<int> adj[3001];
vector<int> ord;
int vis[3001];

void dfs(int no,int par=-1){
	ord.pb(no);
	for(auto j:adj[no]){
		if(j==par){
			continue;
		}
		dfs(j,no);
	}
}
int cur=0;
int st=0;
int kk;
void dfs2(int no,int par=-1,int par2=-1){
	if(par2==-1){
		for(auto j:adj[no]){

			if(vis[j]){
				dfs2(j,no,j);
			}
		}
	}
	else{
		if(dist[no][kk]==dist[no][par2]){
			col[kk]=col[no];
			st=1;
			return;
		}
		for(auto j:adj[no]){
			if(par==j){
				continue;
			}
			if(vis[j]){
				dfs2(j,no,par2);
			}
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int te;
	cin>>te;
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		par[i]=i;
		for(int j=0;j<n;j++){
			cin>>dist[i][j];
		}
	}

	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(dist[i][j]==1){
				int x=find(i);
				int y=find(j);
				par[x]=y;
			}
		}
	}
	map<int,vector<int>> ss;
	for(int i=0;i<n;i++){
		find(i);
		ss[par[i]].pb(i);
	}
	vector<pair<int,int>> ans;
	vector<int> tt;
	for(auto j:ss){
		for(int i=0;i<j.b.size()-1;i++){
			ans.pb({j.b[i],j.b[i+1]});
		}
		tt.pb(j.a);
	}
	for(int i=0;i<tt.size();i++){
		for(int j=i+1;j<tt.size();j++){
			int x=find(tt[i]);
			int y=find(tt[j]);
			if(x==y){
				continue;
			}
			if(dist[tt[i]][tt[j]]==2){
				par[x]=y;
				ans.pb({tt[i],tt[j]});
			}
		}
	}
	for(auto j:ans){
		adj[j.a].pb(j.b);
		adj[j.b].pb(j.a);
	}
	dfs(0);

	for(auto j:ord){
//		cout<<j<<',';
//		cur.clear();
		kk=j;
		st=0;
		dfs2(j);
		if(st==0){
			cur+=1;
			col[j]=cur;
		}
		vis[j]=1;

	}
//	cout<<endl;
/*	for(auto j:ss){
		for(int i=0;i<j.b.size()-1;i++){
			col[j.b[i]]=col[j.b.back()];
		}
		//tt.pb(j.b.back());
	}*/
	for(int i=0;i<n;i++){

		cout<<col[i]<<" ";
		
	}
	cout<<endl;
	for(auto j:ans){
		cout<<j.a+1<<" "<<j.b+1<<endl;
	}







	return 0;
}

Compilation message (stderr)

izlet.cpp: In function 'int main()':
izlet.cpp:90:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<j.b.size()-1;i++){
               ~^~~~~~~~~~~~~
izlet.cpp:95:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tt.size();i++){
              ~^~~~~~~~~~
izlet.cpp:96:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=i+1;j<tt.size();j++){
                 ~^~~~~~~~~~

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