Submission #1202138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202138		WH8	KOVANICE (COI15_kovanice)	C++20	0 / 100	197 ms	41820 KiB

kovanice

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define f first
#define s second
#define pll pair<int,int>
#define pb push_back
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
int n,m,v,p[300005];
vector<vector<int>> al(300005), ral(300005);
int in[300005], rin[300005];
vector<int> dep(300005,-1), rdep(300005,-1);
vector<pll> ed;
int par(int x){
	if(p[x]==0)return x;
	return p[x]=par(p[x]);
}
void merge(int a,int b){
	int x=par(a),y=par(b);
	if(x==y)return;
	p[x]=y;
}

void dfs(int x, vector<vector<int>> & ad, vector<int> & dp){
	//~ printf("at %lld\n",x);
	for(auto it:ad[x]){
		if(dp[it]==-1)dfs(it,ad,dp);
		dp[x]=max(dp[x], dp[it]+1);
	}
}

signed main(){
	cin>>n>>m>>v;
	for(int i=0;i<v;i++){
		int a,b;
		char c;
		cin>>a>>c>>b;
		if(c=='='){
			merge(a,b);
		}
		else {
			if (c=='>')swap(a,b);
			ed.pb({a,b});
		}
	}
	for(auto [a,b]:ed){
		//~ printf("%lld %lld\n",par(a),par(b));
		al[par(a)].pb(par(b));
		in[par(b)]++;
		ral[par(b)].pb(par(a));
		rin[par(a)]++;
	}
	vector<int> root, rroot;
	for(int i=1;i<=m;i++){
		if(i==par(i) and in[i]==0)root.pb(i);
		if(i==par(i) and rin[i]==0)rroot.pb(i);
	}
	//~ for(auto it:root)cout<<it<<endl;
	//~ return 0;
	for(auto it:root)rdep[it]=0;
	for(auto it:rroot)dep[it]=0;
	for(auto it:root) dfs(it, al, dep);
	for(auto it:rroot) dfs(it, ral, rdep);
	for(int i=1;i<=m;i++){
		if(dep[par(i)]+rdep[par(i)]==n-1){
			cout<<'K'<<dep[par(i)]+1<<"\n";
		}
		else cout<<"?\n";
	}
}
/*
4 5 4
1>2
2>3
3>4
5>3
*/

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