oj.uz

Submission #128309

# Submission time Handle Problem Language Result Execution time Memory
128309 2019-07-10T16:30:28 Z Adhyyan1252 KOVANICE (COI15_kovanice) C++11
100 / 100
 1355 ms 41316 KB 
#include<bits/stdc++.h>

using namespace std;

int n, m, v; 

vector<int> par;

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 true;
}

vector<vector<int> > in, out;
vector<int> low, high;

vector<int> o;
vector<int> vis;
void dfs(int cur){
	if(vis[cur]) return;
	for(int u: out[cur]){
		dfs(u);
	}
	o.push_back(cur);
	vis[cur] = 1;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>m>>v;
	
	par = vector<int>(m, -1);
	
	vector<pair<int, int> > op;
	for(int i = 0; i < v; i++){
		int a, b; char c; cin>>a>>c>>b; a--, b--;
		if(c == '='){
			merge(a, b);
		}else{
			op.push_back({a, b});
		}
	}
	
	for(auto& x: op){
		x.first = find(x.first);
		x.second = find(x.second);
		assert(x.first != x.second);
	}
	
	in.resize(m);
	out.resize(m);
	low = vector<int>(m, 0);
	high = vector<int>(m, n-1);
	
	for(auto x: op){
		out[x.first].push_back(x.second);
		in[x.second].push_back(x.first);
	}
	
	vis = vector<int>(m, 0);
	for(int i = 0; i < m; i++) if(find(i) == i)dfs(i);
	
	reverse(o.begin(), o.end());
	for(int u: o){
		//cout<<"O : "<<u<<endl;
		for(int v: out[u]){
			low[v] = max(low[v], low[u] + 1);
		}
	}
	reverse(o.begin(), o.end());
	for(int u: o){
		for(int v: in[u]){
			high[v] = min(high[v], high[u] - 1);
		}
	}
	
	for(int i = 0; i < m; i++){
		int u = find(i);
		if(low[u] == high[u]){
			cout<<"K"<<low[u]+1<<endl;
		}else{
			//cout<<u<<": "<<low[u]+1<<" "<<high[u]+1<<endl;
			cout<<"?"<<endl;
		}
		assert(low[u] <= high[u]);
	}
	
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 18632 KB Output is correct
2 Correct 642 ms 18680 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3056 KB Output is correct
2 Correct 30 ms 3060 KB Output is correct
3 Correct 31 ms 3052 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1193 ms 35420 KB Output is correct
2 Correct 1170 ms 34468 KB Output is correct
3 Correct 1172 ms 34380 KB Output is correct
4 Correct 1231 ms 40648 KB Output is correct
5 Correct 1355 ms 41316 KB Output is correct