Submission #128309

#	Time	Username	Problem	Language	Result	Execution time	Memory
128309		Adhyyan1252	KOVANICE (COI15_kovanice)	C++11	100 / 100	1355 ms	41316 KiB

kovanice

#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 / 10
• Subtask 2: 40 / 40
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40