제출 #1232592

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1232592		lopkus	KOVANICE (COI15_kovanice)	C++20	100 / 100	151 ms	66140 KiB

kovanice

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<long long, long long>
using namespace std;

const int MAX = 3e5 + 5;
int parent[MAX];
int depth[MAX];
set<int> edges1[MAX];
set<int> edges2[MAX];
vector<int> degree1(MAX);
vector<int> degree2(MAX);
vector<int> dp1(MAX);
vector<int> dp2(MAX);

int get(int a) {
    while (a != parent[a]) a = parent[a];
    return a;
}

void join(int a, int b){
    a = get(a);
    b = get(b);
    if (a == b) return;
    if (depth[a] > depth[b]) swap(a, b);
    parent[a] = b;
    depth[b] += depth[a];
    return;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, v, a, b;
    cin >> n >> m >> v;
    char c;
    vector<pii> vp;

    for (int i = 1; i <= m; i++) {
        parent[i] = i;
        depth[i] = 1;
    }

    for (int i = 0; i < v; i++) {
        string s;
        cin >> s;
        s.push_back('+');
        int pos = 0, a = 0, b = 0;
        while(s[pos] >= '0' && s[pos] <= '9') {
            a *= 10;
            a += s[pos++] - '0';
        }

        c = s[pos++];

        while(s[pos] >= '0' && s[pos] <= '9') {
            b *= 10;
            b += s[pos++] - '0';
        }

        if (c == '=') join(a, b);
        else if (c == '<') vp.push_back({a, b});
        else vp.push_back({b, a});
    }

    for (auto e : vp) {
        int a = get(e.fi);
        int b = get(e.se);
        if (!edges1[a].count(b)) {
            edges1[a].insert(b);
            degree1[b]++;
        }

        if (!edges2[b].count(a)) {
            edges2[b].insert(a);
            degree2[a]++;
        }
    }

    queue<int> q;
    for (int i = 1; i <= m; i++) {
        if (i != get(i)) continue;
        if (degree1[get(i)] == 0) q.push(i);
    }

    while(!q.empty()) {
        a = q.front();
        q.pop();
        dp1[a] += 1;
        for (auto e : edges1[a]) {
            dp1[e] = max(dp1[e], dp1[a]);
            degree1[e]--;
            if (degree1[e] == 0) q.push(e);
        }

    }

    for (int i = 1; i <= m; i++) {
        if (i != get(i)) continue;
        if (degree2[get(i)] == 0) q.push(i);
    }

    while(!q.empty()) {
        a = q.front();
        q.pop();
        dp2[a] += 1;
        for (auto e : edges2[a]) {
            dp2[e] = max(dp2[e], dp2[a]);
            degree2[e]--;
            if (degree2[e] == 0) q.push(e);
        }
    }

    for (int i = 1; i <= m; i++) {
        int a = get(i);
        if (dp1[a] + dp2[a] == n + 1) cout << "K" << dp1[a] << "\n";
        else cout << "?\n";
    }

    return 0;
}

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