oj.uz

Submission #846340

# Submission time Handle Problem Language Result Execution time Memory
846340 2023-09-07T13:42:54 Z vjudge1 KOVANICE (COI15_kovanice) C++17
100 / 100
 521 ms 67736 KB 
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
#define N 300005
using namespace std;
int par[N], topoDis[N], vis[N];
vector <vector<int> > adj(N), revadj(N);
vector <int> zeros, edgecnt(N);
vector <int> ans(N, -1);

int parent(int x) {
	if(par[x] == x) return x;
	return par[x] = parent(par[x]);
}

void merge(int a, int b) {
	a = parent(a);
	b = parent(b);
	par[a] = b;
}

void dfsForAns(int node) {
	ans[node] = topoDis[node];
	vis[node] = 1;
	for(auto it:revadj[node]) {
		if(vis[it] or topoDis[it] != topoDis[node] - 1) continue;
		dfsForAns(it);
	}
}

int32_t main(){
	fast
	int n, m, v;
	cin>>n>>m>>v;
	vector <pair<int,int> > input;
	for(int i = 0; i < m; i++) // pre-pre-pre-calculate
		par[i] = i;
	for(int i = 0; i < v; i++) { // pre-pre-calculation of dsu
		int a, b;
		char comp;
		cin>>a>>comp>>b;
		a--, b--;
		if(comp == '=') {
			merge(a, b);
			continue;
		}
		if(comp == '>') swap(a, b); 
		input.push_back({a, b});
	}
	set <pair<int, int> > st;
	for(int i = 0; i < m; i++) // pre-calculate
		parent(i);
	for(auto it:input) {
		int a = it.first, b = it.second;
		a = par[a], b = par[b];
		if( st.count(make_pair(a, b)) ) continue;

		adj[a].push_back(b);
		revadj[b].push_back(a);
		st.insert(make_pair(a, b));

		edgecnt[b]++;
	}

	// --- took the inputs

	for(int i = 0; i < m; i++) {
		if(!edgecnt[i]) {
			zeros.push_back(i);
			topoDis[i] = 1; // bunun maxını al dikkat et
		}
	}

	while(!zeros.empty()) {
		int node = zeros.back();
		zeros.pop_back();
		for(auto it:adj[node]) {
			edgecnt[it]--;
			topoDis[it] = max(topoDis[it], topoDis[node] + 1);
			if(!edgecnt[it]) {
				zeros.push_back(it);
			}
		}
	}
	for(int i = 0; i < m; i++) {
		if(topoDis[i] == n) {
			dfsForAns(i);
		}
	}

	for(int i = 0; i < m; i++) {
		if(!~ans[par[i]]) cout<<"?\n";
		else cout<<"K"<<ans[par[i]]<<"\n";
	}	
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 23388 KB Output is correct
2 Correct 7 ms 23388 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 34184 KB Output is correct
2 Correct 97 ms 34636 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 25032 KB Output is correct
2 Correct 33 ms 26064 KB Output is correct
3 Correct 38 ms 27596 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 54776 KB Output is correct
2 Correct 338 ms 54492 KB Output is correct
3 Correct 318 ms 55092 KB Output is correct
4 Correct 521 ms 64400 KB Output is correct
5 Correct 483 ms 67736 KB Output is correct