제출 #1318042

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318042		noobsolver24	KOVANICE (COI15_kovanice)	C++20	100 / 100	356 ms	48948 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 dis[sz], disr[sz];
bool vis1[sz], vis2[sz];
vector<int> g[sz], gr[sz], tp, tpr;

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 dfs1(int node){
    vis1[node] = 1;
    for (int to : g[node]) {
        if (!vis1[to]) {
            dfs1(to);
        }
    }
    tp.push_back(node);
}

void dfs2(int node){
    vis2[node] = 1;
    for (int to : gr[node]) {
        if (!vis2[to]) {
            dfs2(to);
        }
    }
    tpr.push_back(node);
}

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++) {
        int a, b;
        char op;
        cin >> a >> op >> b;
        if (op == '=') {
			dsu.unite(a, b);
		} else {
			ed.push_back({a, b});
		}
    }
    for (auto [x, y] : ed) {
		x = dsu.find(x);
		y = dsu.find(y);
		g[x].push_back(y);
        gr[y].push_back(x);
	}
    for (int i = 1; i <= m; i++) {
        int r = dsu.find(i);
        if (!vis1[r]) {
            dfs1(r);
        }
    }
    for (int i = 1; i <= m; i++) {
        int r = dsu.find(i);
        if (!vis2[r]) {
            dfs2(r);
        }
    }
    reverse(all(tp));
    reverse(all(tpr));
    for (auto x : tp) {
        for (auto to : g[x]) {
            dis[to] = max(dis[to], dis[x] + 1);
        }
    }
    for (auto x : tpr) {
        for (auto to : gr[x]) {
            disr[to] = max(disr[to], disr[x] + 1);
        }
    }
    for (int i = 1; i <= m; i++) {
        int r = dsu.find(i);
        if (dis[r] + disr[r] + 1 < n) {
            cout << "?" << endl;
        } else cout << "K" << dis[r] + 1 << endl;
    }
}

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

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