Submission #846340

#	Time	Username	Problem	Language	Result	Execution time	Memory
846340		vjudge1	KOVANICE (COI15_kovanice)	C++17	100 / 100	521 ms	67736 KiB

kovanice

#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 / 10
• Subtask 2: 40 / 40
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40