Submission #1135849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135849		Pwo	KOVANICE (COI15_kovanice)	C++20	100 / 100	224 ms	42256 KiB

kovanice

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

int n, m, q, p[300005], sz[300005], ans[300005], in[300005], depth[300005];
vector<pair<int, int>> x;
vector<int> g[300005], r[300005];
int mn[300005], mx[300005];
bool visited[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) {
	if (visited[v]) return;
	visited[v] = 1;
	mn[v] = 1;
	for (const int u : r[v]) {
		dfs(u);
		mn[v] = max(mn[u] + 1, mn[v]);
	}	
}

void dfs2(int v) {
	if (visited[v]) return;
	visited[v] = 1;
	mx[v] = n;
	for (const int u : g[v]) {
		dfs2(u);
		mx[v] = min(mx[u] - 1, mx[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 x.emplace_back(a, b);
	}
	
	for (const auto [a, b] : x) {
		int _a = find(a), _b = find(b);
		g[_a].push_back(_b);
		r[_b].push_back(_a);
		
	}
	
	for (int i = 1; i <= m; i++) {
		int z = find(i);
		if (!visited[z]) dfs(z);
	}
	memset(visited, 0, sizeof(visited));
	for (int i = 1; i <= m; i++) {
		int z = find(i);
		if (!visited[z]) dfs2(z);
	}
	
	for (int i = 1; i <= m; i++) {
		int y = mn[find(i)], z = mx[find(i)];
		if (y == z) cout << 'K' << y << '\n';
		else cout << "?\n";
	}
}

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