Submission #124199

#	Time	Username	Problem	Language	Result	Execution time	Memory
124199		Adhyyan1252	Izlet (COI19_izlet)	C++11	100 / 100	913 ms	101496 KiB

izlet

#include<bits/stdc++.h>
//https://oj.uz/problem/view/COI19_izlet
using namespace std;

vector<vector<int> > g, a;
int n; 

struct dsu{
	vector<int> par;
	int sz;
	
	dsu(int size){
		sz = size;
		par = vector<int>(size, -1);
	}
	
	int find(int cur){
		if(par[cur] == -1) return cur;
		return par[cur] = find(par[cur]);
	}
	
	bool merge(int a, int b){
		a = find(a);
		b = find(b);
		if(a == b) return false;
		par[b] = a;
		return false;
	}
};


vector<int> col;
vector<vector<int> > ans;
vector<int> f;
int ncol = -1;
void dfs2(int cur, int par, int lead){
	if(par != -1 && f[col[cur]] == 0 && a[lead][cur] == a[lead][par]){
		//found the new color
		ncol = col[cur];
		return;
	}
	if(par != -1)f[col[cur]]++;
	for(int u: ans[cur]){
		if(u == par) continue;
		if(ncol != -1) break;
		dfs2(u, cur, lead);
	}
	if(par != -1)f[col[cur]]--;
}

int diff = 0;

void dfs1(int cur){
	
	//first figure out its color
	ncol = -1;
	dfs2(cur, -1, cur);
	if(ncol == -1){
		col[cur] = diff; diff++;
	}else{
		col[cur] = ncol;
	}
	for(int u: g[cur]){
		if(col[u] == -1){ //unvisited
			ans[cur].push_back(u);
			ans[u].push_back(cur);
			dfs1(u);
		}
	}
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	int sub; cin>>sub;
	cin>>n;
	a = vector<vector<int> > (n, vector<int>(n));
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin>>a[i][j];
		}
	}
	
	dsu same(n);
	for(int i = 0; i < n; i++){
		for(int j = i+1; j < n; j++){
			if(a[i][j] == 1){
				same.merge(i, j);
			}
		}
	}
	//cerr<<"MERGING DONE"<<endl;
	g.resize(n);
	for(int i = 0; i < n; i++){
		for(int j = i+1; j < n; j++){
			int id = same.find(i);
			int jd = same.find(j);
			if(id == jd) continue;
			if(id != i || jd != j) continue;
			if(a[id][jd] == 2){
				g[id].push_back(jd);
				g[jd].push_back(id);
			}
		}
	}
	//cerr<<"NEW GRAPH MADE"<<endl;
	col = vector<int>(n, -1);
	ans.resize(n);
	f.resize(n);
	dfs1(0);
//	for(int i = 0; i < n; i++){
//		if(same.find(i) != i) continue;
//		cout<<i<<" "<<col[i]<<" : : ";
//		for(int u: ans[i]){
//			cout<<u<<" ";
//		}
//		cout<<endl;
//	}
	vector<pair<int, int> > tree;
	for(int i = 0; i < n; i++){
		if(i != same.find(i)) continue;
		for(int u: ans[i]){
			if(u > i) tree.push_back({u, i});
		}
	}
	for(int i = 0; i < n; i++){
		if(i == same.find(i)) continue;
		tree.push_back({i, same.find(i)});
		col[i] = col[same.find(i)];
	}
	
	for(int i = 0; i < n; i++){
		cout<<col[i]+1<<" ";
	}
	cout<<endl;
	assert(tree.size() == n-1);
	for(int i = 0; i < tree.size(); i++){
		cout<<tree[i].first+1<<" "<<tree[i].second+1<<endl;
	}
}

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from izlet.cpp:1:
izlet.cpp: In function 'int main()':
izlet.cpp:135:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(tree.size() == n-1);
         ~~~~~~~~~~~~^~~~~~
izlet.cpp:136:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < tree.size(); i++){
                 ~~^~~~~~~~~~~~~

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