Submission #467094

#	Time	Username	Problem	Language	Result	Execution time	Memory
467094		SirCovidThe19th	KOVANICE (COI15_kovanice)	C++17	100 / 100	988 ms	36892 KiB

kovanice

#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 / 10
• Subtask 2: 40 / 40
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40