oj.uz

Submission #467094

# Submission time Handle Problem Language Result Execution time Memory
467094 2021-08-21T17:18:27 Z SirCovidThe19th KOVANICE (COI15_kovanice) C++17
100 / 100
 988 ms 36892 KB 
#include <bits/stdc++.h>
using namespace std; 

const int mx = 3e5 + 5;

int n, m, k, par[mx], A[mx], B[mx], bst[mx][2]; vector<int> adj[mx][2];

int get(int i){
    return i == par[i] ? par[i] : par[i] = get(par[i]);
}
void merge(int a, int b){
    par[get(a)] = get(b);
}
void dfs(int i, int dr){
    for (auto x : adj[i][dr]){
        if (!bst[x][dr]) dfs(x, dr);
        bst[i][dr] = max(bst[i][dr], bst[x][dr] + 1);
    }
}

int main(){
	cin >> n >> m >> k; iota(par, par + m + 1, 0);
    for (int i = 0; i < k; i++){
        char c; cin >> A[i] >> c >> B[i];
        if (c == '=') merge(A[i], B[i]), A[i] = 0;
    }
    for (int i = 0; i < k; i++) if (A[i]){
        int a = get(A[i]), b = get(B[i]);
        adj[a][0].push_back(b); adj[b][1].push_back(a);
    }
    for (int i = 1; i <= m; i++){
        int x = get(i); dfs(x, 0); dfs(x, 1);
        cout<<(bst[x][0] + bst[x][1] + 1 == n ? "K" + to_string(bst[x][1] + 1) : "?")<<endl;
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 21792 KB Output is correct
2 Correct 453 ms 21972 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 17092 KB Output is correct
2 Correct 74 ms 17036 KB Output is correct
3 Correct 74 ms 17120 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 949 ms 33104 KB Output is correct
2 Correct 941 ms 32164 KB Output is correct
3 Correct 952 ms 32040 KB Output is correct
4 Correct 961 ms 36324 KB Output is correct
5 Correct 988 ms 36892 KB Output is correct