Submission #1317910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317910		noobsolver24	KOVANICE (COI15_kovanice)	C++20	0 / 100	296 ms	29992 KiB

kovanice

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

const int sz = 3e5 + 5, inf = 1e18, mod = 1e9 + 7, lg = 23;

int a[sz], b[sz], in[sz];
int ans[sz];
char op[sz];
vector<int> g[sz];
bool used[sz];

struct DSU {
	int n;
	vector<int> par;
	void init(int _n) {
		n = _n;
		par.assign(n + 1, -1);
	}
	int find(int a){
		if (par[a] < 0) return a;
		return par[a] = find(par[a]);
	}
	bool unite(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b) return 0;
		if (par[a] < par[b]) swap(a, b);
		par[b] += par[a];
		par[a] = b;
		return 1;
	}
};

void dfs(int node, vector<int> &c){
	used[node] = 1;
	c.push_back(node);
	for (int to : g[node]) {
		if (!used[to]) {
			dfs(to, c);
		}
	}
}

void _(){
    int n, m, v;
    cin >> n >> m >> v;
    DSU dsu;
    dsu.init(m);
	vector<pair<int, int>> ed;
    for (int i = 1; i <= v; i++) {
        cin >> a[i] >> op[i] >> b[i];
        if (op[i] == '=') {
			dsu.unite(a[i], b[i]);
		} else {
			ed.push_back({a[i], b[i]});
		}
    }
    for (auto [x, y] : ed) {
		x = dsu.find(x);
		y = dsu.find(y);
		g[x].push_back(y);
		in[y]++;
	}
	vector<vector<int>> cm;
	for (int i = 1; i <= n; i++) {
		if (dsu.find(i) == i and !used[i]) {
			vector<int> c;
			dfs(i, c);
			cm.push_back(c);
		}
	}
	for (auto v : cm) {
		queue<int> q;
		for (auto x : v) {
			if (!in[x]) {
				q.push(x);
			}
		}
		int w = 0;
		while (q.size()) {
			int cur = q.front();
			ans[cur] = ++w;
			q.pop();
			for (int to : g[cur]) {
				if (--in[to] == 0) {
					q.push(to);
				}
			}
		}
		if (w < n) {
			for (auto x : v) ans[x] = -1;
		}
	}
	for (int i = 1; i <= m; i++) {
		ans[i] = ans[dsu.find(i)];
		if (ans[i] == -1 or ans[i] == 0) cout << "?" << endl;
		else cout << "K" << ans[i] << endl;
	}
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    int T = 1;
    // cin >> T;    
    while (T--) _();
}

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