oj.uz

Submission #124199

# Submission time Handle Problem Language Result Execution time Memory
124199 2019-07-02T16:06:14 Z Adhyyan1252 Izlet (COI19_izlet) C++11
100 / 100
 913 ms 101496 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 794 ms 85652 KB Output is correct
3 Correct 803 ms 101496 KB Output is correct
4 Correct 670 ms 62588 KB Output is correct
5 Correct 723 ms 82936 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 37500 KB Output is correct
2 Correct 705 ms 65928 KB Output is correct
3 Correct 896 ms 74160 KB Output is correct
4 Correct 913 ms 75128 KB Output is correct
5 Correct 655 ms 53872 KB Output is correct
6 Correct 716 ms 60920 KB Output is correct
7 Correct 524 ms 45560 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 794 ms 85652 KB Output is correct
3 Correct 803 ms 101496 KB Output is correct
4 Correct 670 ms 62588 KB Output is correct
5 Correct 723 ms 82936 KB Output is correct
6 Correct 673 ms 37500 KB Output is correct
7 Correct 705 ms 65928 KB Output is correct
8 Correct 896 ms 74160 KB Output is correct
9 Correct 913 ms 75128 KB Output is correct
10 Correct 655 ms 53872 KB Output is correct
11 Correct 716 ms 60920 KB Output is correct
12 Correct 524 ms 45560 KB Output is correct
13 Correct 682 ms 54540 KB Output is correct
14 Correct 809 ms 61688 KB Output is correct
15 Correct 695 ms 54668 KB Output is correct
16 Correct 767 ms 58244 KB Output is correct
17 Correct 761 ms 60152 KB Output is correct
18 Correct 648 ms 54648 KB Output is correct
19 Correct 673 ms 54008 KB Output is correct
20 Correct 669 ms 54776 KB Output is correct
21 Correct 676 ms 54392 KB Output is correct
22 Correct 741 ms 54648 KB Output is correct
23 Correct 674 ms 54392 KB Output is correct
24 Correct 749 ms 60924 KB Output is correct
25 Correct 656 ms 53880 KB Output is correct