oj.uz

Submission #392612

# Submission time Handle Problem Language Result Execution time Memory
392612 2021-04-21T11:10:49 Z BThero KOVANICE (COI15_kovanice) C++17
100 / 100
 777 ms 36720 KB 
// 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14412 KB Output is correct
2 Correct 12 ms 14436 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 23512 KB Output is correct
2 Correct 405 ms 23552 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 17092 KB Output is correct
2 Correct 32 ms 17148 KB Output is correct
3 Correct 32 ms 17044 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 754 ms 35136 KB Output is correct
2 Correct 724 ms 34464 KB Output is correct
3 Correct 732 ms 34264 KB Output is correct
4 Correct 702 ms 36020 KB Output is correct
5 Correct 777 ms 36720 KB Output is correct