Submission #392612

#	Time	Username	Problem	Language	Result	Execution time	Memory
392612		BThero	KOVANICE (COI15_kovanice)	C++17	100 / 100	777 ms	36720 KiB

kovanice

// chrono::system_clock::now().time_since_epoch().count()
#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define debug(x) cerr << #x << " = " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAXN = (int)3e5 + 5;

vector<pii> adj[MAXN];
vi G[MAXN], ord;
bool used[MAXN];
int n, nn, m, q;
int col[MAXN];
int dpA[MAXN], dpB[MAXN];

void dfs0(int v) {
    col[v] = nn;

    for (auto &[to, w] : adj[v]) {
        if (w == 0 && !col[to]) {
            dfs0(to);
        }
    }
}

void dfs1(int v) {
    used[v] = 1;

    for (int to : G[v]) {
        if (!used[to]) {
            dfs1(to);
        }
    }

    ord.pb(v);
}

void solve() {
    cin >> m >> n >> q;

    rep (i, 1, q + 1) {
        int a, b;
        char c;
        cin >> a >> c >> b;
        
        if (c == '=') {
            adj[a].eb(b, 0);
            adj[b].eb(a, 0);
        }
        else {
            adj[a].eb(b, 1);
        }
    }

    rep (i, 1, n + 1) {
        if (!col[i]) {
            ++nn;
            dfs0(i);
        }
    }

    rep (v, 1, n + 1) {
        for (auto &[to, w] : adj[v]) {
            if (w == 1) {
                assert(col[v] != col[to]);
                G[col[v]].pb(col[to]);
            }
        }
    }

    rep (i, 1, nn + 1) {
        if (!used[i]) {
            dfs1(i);
        }
    }

    fill(dpA + 1, dpA + nn + 1, 1);
    fill(dpB + 1, dpB + nn + 1, 1);

    for (int v : ord) {
        for (int to : G[v]) {
            dpB[v] = max(dpB[v], dpB[to] + 1);
        }
    }

    reverse(all(ord));

    for (int v : ord) {
        for (int to : G[v]) {
            dpA[to] = max(dpA[to], dpA[v] + 1);
        }
    }

    for (int i = 1; i <= n; i++) {
        int j = col[i];

        if (dpA[j] + dpB[j] - 1 == m) {
            cout << "K" << dpA[j] << endl;
        }
        else {
            cout << "?" << endl;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tt = 1;

    for (int i = 1; i <= tt; ++i) {
        solve();
    }

    return 0;
}

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