oj.uz

Submission #239468

# Submission time Handle Problem Language Result Execution time Memory
239468 2020-06-15T18:13:57 Z kshitij_sodani Izlet (COI19_izlet) C++17
100 / 100
 856 ms 61816 KB 
#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

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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 730 ms 36472 KB Output is correct
3 Correct 720 ms 36272 KB Output is correct
4 Correct 594 ms 36136 KB Output is correct
5 Correct 625 ms 36216 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 36332 KB Output is correct
2 Correct 610 ms 36344 KB Output is correct
3 Correct 778 ms 36472 KB Output is correct
4 Correct 853 ms 36600 KB Output is correct
5 Correct 563 ms 36088 KB Output is correct
6 Correct 658 ms 36216 KB Output is correct
7 Correct 490 ms 30840 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 730 ms 36472 KB Output is correct
3 Correct 720 ms 36272 KB Output is correct
4 Correct 594 ms 36136 KB Output is correct
5 Correct 625 ms 36216 KB Output is correct
6 Correct 607 ms 36332 KB Output is correct
7 Correct 610 ms 36344 KB Output is correct
8 Correct 778 ms 36472 KB Output is correct
9 Correct 853 ms 36600 KB Output is correct
10 Correct 563 ms 36088 KB Output is correct
11 Correct 658 ms 36216 KB Output is correct
12 Correct 490 ms 30840 KB Output is correct
13 Correct 677 ms 36216 KB Output is correct
14 Correct 856 ms 61816 KB Output is correct
15 Correct 570 ms 53624 KB Output is correct
16 Correct 666 ms 58104 KB Output is correct
17 Correct 671 ms 60152 KB Output is correct
18 Correct 621 ms 54008 KB Output is correct
19 Correct 655 ms 53880 KB Output is correct
20 Correct 596 ms 53880 KB Output is correct
21 Correct 643 ms 54648 KB Output is correct
22 Correct 669 ms 54140 KB Output is correct
23 Correct 670 ms 54520 KB Output is correct
24 Correct 680 ms 61044 KB Output is correct
25 Correct 611 ms 54008 KB Output is correct