Submission #674787

#	Time	Username	Problem	Language	Result	Execution time	Memory
674787		MilosMilutinovic	KOVANICE (COI15_kovanice)	C++14	100 / 100	196 ms	43560 KiB

kovanice

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using llf = long double;
using pi = array<int, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()

const int MAXN = 300005;

struct disj {
    int par[MAXN];
    disj() {
        for (int i = 0; i < MAXN; i++) par[i] = i;
    }
    int root(int x) {
        return par[x] == x ? x : par[x] = root(par[x]);
    }
    void unite(int x, int y) {
        par[root(x)] = root(y);
    }
} d;

vector<int> my[MAXN], sm[MAXN];
int deg[MAXN], dep[MAXN];

void adde(int x, int y) {
    deg[x]++;
}

bool vis[MAXN];
int ans[MAXN];

void dfs(int v, int dg) {
    ans[v] = dg;
    vis[v] = true;
    for (int u : sm[v]) {
        if (!vis[u] && dep[u] + 1 == dep[v]) {
            dfs(u, dg - 1);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < k; i++) {
        string s;
        cin >> s;
        int p = 0;
        while (s[p] != '<' && s[p] != '>' && s[p] != '=') p++;
        int l = 0, r = 0;
        for (int j = 0; j < p; j++) l = (l * 10) + (s[j] - '0');
        for (int j = p + 1; j < sz(s); j++) r = (r * 10) + (s[j] - '0');
        if (s[p] == '=') {
            d.unite(l, r);
        } else if (s[p] == '<') {
            my[r].push_back(l);
        } else {
            my[l].push_back(r);
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j : my[i]) {
            sm[d.root(i)].push_back(d.root(j));
        }
    }
    for (int i = 1; i <= m; i++) if (d.root(i) == i) {
        sort(all(sm[i]));
        sm[i].erase(unique(all(sm[i])), sm[i].end());
        for (int j : sm[i]) adde(j, i);
    }
    vector<int> que;
    for (int i = 1; i <= m; i++) if (deg[i] == 0) {
        que.push_back(i);
    }
    for (int b = 0; b < sz(que); b++) {
        int x = que[b];
        for (int y : sm[x]) {
            deg[y]--;
            if (deg[y] == 0) que.push_back(y);
        }
    }
    reverse(all(que));
    for (int b = 0; b < sz(que); b++) {
        int x = que[b];
        dep[x] = 1;
        for (int y : sm[x]) dep[x] = max(dep[x], dep[y] + 1);
    }
    for (int i = 1; i <= m; i++) {
        if (dep[i] == n) dfs(i, n);
    }
    for (int i = 1; i <= m; i++) ans[i] = ans[d.root(i)];
    for (int i = 1; i <= m; i++) {
        if (ans[i] == 0) {
            cout << "?\n";
        } else {
            cout << "K" << ans[i] << "\n";
        }
    }
    return 0;
}

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