Submission #1135185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135185		emptypringlescan	KOVANICE (COI15_kovanice)	C++17	50 / 100	2094 ms	26040 KiB

kovanice

#include <bits/stdc++.h>
using namespace std;
int par[300005];
vector<int> adj[2][300005];
int val[2][300005];
int n,m,v;
int find(int x){
	if(par[x]==x) return x;
	return par[x]=find(par[x]);
}
void merge(int x, int y){
	x=find(x); y=find(y);
	par[x]=y;
}
void forward(int x){
	val[0][x]=n;
	for(int i:adj[0][x]){
		forward(i);
		val[0][x]=min(val[0][x],val[0][i]-1);
	}
}
void backward(int x){
	val[1][x]=1;
	for(int i:adj[1][x]){
		backward(i);
		val[1][x]=max(val[1][x],val[1][i]+1);
	}
}

int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m >> v;
	vector<pair<int,int> > ed;
	for(int i=0; i<=m; i++) par[i]=i;
	for(int i=0; i<v; i++){
		int a,b;
		char c;
		cin >> a >> c >> b;
		if(c=='='){
			merge(a,b);
			continue;
		}
		else if(c=='>') swap(a,b);
		ed.push_back({a,b});
	}
	for(auto [a,b]:ed){
		a=find(a); b=find(b);
		adj[0][a].push_back(b);
		adj[1][b].push_back(a);
	}
	for(int i=1; i<=m; i++){
		if(!val[0][find(i)]) forward(find(i));
		if(!val[1][find(i)]) backward(find(i));
	}
	for(int i=1; i<=m; i++){
		if(val[0][find(i)]==val[1][find(i)]){
			cout << 'K' << val[0][find(i)] << '\n';
		}
		else cout << "?\n";
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 0 / 10
• Subtask 4: 0 / 40