Submission #388234

#	Time	Username	Problem	Language	Result	Execution time	Memory
388234		negar_a	KOVANICE (COI15_kovanice)	C++14	100 / 100	462 ms	44872 KiB

kovanice

//!yrt tsuj uoy srettam gnihton no emoc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second

const int maxn = 3e5 + 10;
vector <int> in[maxn], out[maxn];
vector <int> top;
bool mark[maxn];
int ans[maxn], dp[maxn], inc[maxn];
int par[maxn];

void dfs(int v){
	mark[v] = true;
	for(int u : out[v]){
		if(!mark[u]){
			dfs(u);
		}
	}
	top.pb(v);
}
void sfd(int v){
	mark[v] = true;
	for(int u : in[v]){
		if(dp[u] == dp[v] - 1 && !mark[u]){
			sfd(u);
		}
	}
}

void bfs(int u){
	queue <int> q;
	q.push(u);
	dp[u] = 1;
	while(q.size()){
		int v = q.front();
		mark[v] = true;
		q.pop();
		for(int w : out[v]){
			inc[w] ++;
			dp[w] = max(dp[w], dp[v] + 1);
			if(inc[w] == (int)in[w].size()){
				q.push(w);
			}
		}
	}
}

int find_par(int x){
	if(x == par[x]){
		return x;
	}
	return par[x] = find_par(par[x]);	
}
void merge(int x, int y){
	par[find_par(x)] = find_par(y);
}

int main(){
	fast_io;
	int n, m, v;
	cin >> n >> m >> v;
	vector <pii> ed;
	for(int i = 0; i < m; i ++){
		par[i] = i;
	}
	for(int i = 0; i < v; i ++){
		int x, y;
		char c;
		cin >> x >> c >> y;
		x --; y --;
		if(c == '='){
			if(find_par(x) != find_par(y)){
				merge(x, y);
			}
		}else{
			ed.pb({x, y});
		}
	}
	for(auto p : ed){
		out[find_par(p.F)].pb(find_par(p.S));
		in[find_par(p.S)].pb(find_par(p.F));
	}
	for(int i = 0; i < m; i ++){
		if(!mark[i]){
			dfs(i);
		}
	}
	reverse(top.begin(), top.end());
	memset(mark, 0, sizeof(mark));
	for(int u : top){
		if(inc[u] == (int)in[u].size() && !mark[u]){
//			cout << "u! " << u << endl;
			bfs(u);
		}
	}
	memset(mark, 0, sizeof(mark));
	for(int i = 0; i < m; i ++){
		if(dp[i] == n){
			sfd(i);
		}
//		cout << i << " : " << dp[i] << endl;
	}
	
	for(int i = 0; i < m; i ++){
//		cout << i << " " << find_par(i) << endl;
		if(mark[find_par(i)]){
			cout << "K" << dp[find_par(i)] << '\n';
		}else{
			cout << "?" << '\n';
		}
	}
	
	return 0;
}

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