oj.uz

Submission #388234

# Submission time Handle Problem Language Result Execution time Memory
388234 2021-04-10T15:50:44 Z negar_a KOVANICE (COI15_kovanice) C++14
100 / 100
 462 ms 44872 KB 
//!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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14796 KB Output is correct
2 Correct 10 ms 14796 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 22724 KB Output is correct
2 Correct 126 ms 23068 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 17316 KB Output is correct
2 Correct 32 ms 17316 KB Output is correct
3 Correct 33 ms 17368 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 33852 KB Output is correct
2 Correct 338 ms 33532 KB Output is correct
3 Correct 315 ms 33236 KB Output is correct
4 Correct 425 ms 39620 KB Output is correct
5 Correct 462 ms 44872 KB Output is correct