Submission #1135554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135554		Pwo	KOVANICE (COI15_kovanice)	C++20	0 / 100	198 ms	21456 KiB

kovanice

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, m, q, p[300005], ans[300005];
vector<int> g[300005], topo;
bool visited[300005], z[300005];
vector<pair<int, int>> x;

int find(int v) {
	if (p[v] == v) return v;
	return p[v] = find(p[v]);
}

void merge(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;
	if (ans[u]) swap(u, v);
	p[u] = v;
}

void dfs(int v) {
	visited[v] = 1;
	for (const int u : g[v])
		if (!visited[u]) dfs(u);
	topo.push_back(v);
}
	

int32_t main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) p[i] = i;
	while (q--) {
		char c; int a, b; string s; cin >> s;
		stringstream os(s);
		os >> a >> c >> b;
		if (c == '=') x.emplace_back(a, b);
		else g[a].push_back(b), z[b] = 1;
	}
	
	for (int i = 1; i <= m; i++) {
		if (z[i] || visited[i]) continue;
		topo.clear(); dfs(i);
		if ((int) topo.size() >= n) {
			for (size_t j = 0; j < topo.size(); j++)
				ans[topo[j]] = n - j;
		}
	}
	
	for (const auto &[a, b] : x) merge(a, b);
	
	for (int i = 1; i <= m; i++) {
		int res = ans[find(i)];
		if (res == 0) cout << "?\n";
		else cout << 'K' << res << '\n';
	}
}

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