Submission #1187475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187475		askarica	KOVANICE (COI15_kovanice)	C++20	0 / 100	48 ms	39860 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;
        a = s[0] - '0';
        b = s[2] - '0';
        c = s[1];
        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: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 10
• Subtask 4: 0 / 40