Submission #1135561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135561		Pwo	KOVANICE (COI15_kovanice)	C++20	0 / 100	300 ms	24044 KiB

kovanice

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

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

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 (sz[v] < sz[u]) swap(u, v);
	p[u] = v;
	sz[v] += sz[u];
}

void dfs(int v) {
	visited[v] = 1;
	for (const int u : g[v]) {
		depth[u] = max(depth[u], depth[v] + 1);
		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, sz[i] = 1;
	while (q--) {
		char c; int a, b; string s; cin >> s;
		stringstream os(s);
		os >> a >> c >> b;
		if (c == '=') merge(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) {
			reverse(topo.begin(), topo.end());
			int cnt = 1;
			for (size_t j = 0; j < topo.size(); j++) {
				if (j > 0 && depth[topo[j]] == depth[topo[j - 1]]) {
					merge(topo[j], topo[j - 1]);
					continue;
				}
				ans[find(topo[j])] = cnt++;
			}
		}
	}
	
	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