Submission #384265

#	Time	Username	Problem	Language	Result	Execution time	Memory
384265		negar_a	KOVANICE (COI15_kovanice)	C++14	60 / 100	418 ms	95712 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 = 1e6;
vector <int> adj[maxn], in[maxn], out[maxn];
vector <int> top;
bool mark[maxn];
int ans[maxn], dp[maxn], inc[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 put(int v, int val){
	mark[v] = true;
	ans[v] = val;
	for(int u : adj[v]){
		if(!ans[u]){
			put(u, val);
		}
	}
}

void bfs(int u){
	queue <int> q;
	q.push(u);
	dp[u] = 1;
	while(q.size()){
		int v = q.front();
		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 main(){
	fast_io;
	int n, m, v;
	cin >> n >> m >> v;
	for(int i = 0; i < v; i ++){
		int x, y;
		char c;
		cin >> x >> c >> y;
		x --; y --;
		if(c == '='){
			adj[x].pb(y);
			adj[y].pb(x);
		}else{
			out[x].pb(y);
			in[y].pb(x);
		}
	}
	for(int i = 0; i < m; i ++){
		if(!mark[i]){
			dfs(i);
		}
	}
	reverse(top.begin(), top.end());
	for(int u : top){
		if(inc[u] == (int)in[u].size() && !dp[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 ++){
		if(mark[i] && !ans[i]){
			put(i, dp[i]);
		}
	}
	for(int i = 0; i < m; i ++){
		if(ans[i]){
			cout << "K" << ans[i] << '\n';
		}else{
			cout << "?" << '\n';
		}
	}
	
	return 0;
}

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