제출 #1305257

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305257		yhkhoo	KOVANICE (COI15_kovanice)	C++20	100 / 100	160 ms	26800 KiB

kovanice

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300000;

int n, m, v;
int p[MAXN], e1[MAXN], e2[MAXN], dp1[MAXN], dp2[MAXN];
basic_string<int> al1[MAXN], al2[MAXN];

int get_parent(int x){
    if(p[x] == x) return x;
    p[x] = get_parent(p[x]);
    return p[x];
}

bool union_set(int u, int v){
    u = get_parent(u);
    v = get_parent(v);
    if(u==v) return 0;
    p[u] = v;
    return 1;
}

int dfs1(int x){
    if(dp1[x] != -1) return dp1[x];
    dp1[x] = 0;
    for(auto nx: al1[x]){
        dp1[x] = max(dp1[x], dfs1(nx)+1);
    }
    return dp1[x];
}

int dfs2(int x){
    if(dp2[x] != -1) return dp2[x];
    dp2[x] = 0;
    for(auto nx: al2[x]){
        dp2[x] = max(dp2[x], dfs2(nx)+1);
    }
    return dp2[x];
}

int main(){
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m >> v;
    for(int i=0; i<m; i++){
        p[i] = i;
    }
    int lc=0;
    char c;
    for(int i=0,a,b; i<v; i++){
        cin >> a >> c >> b;
        a--; b--;
        if(c == '='){
            union_set(a, b);
        }
        else{
            e1[lc] = a;
            e2[lc] = b;
            lc++;
        }
    }
    for(int i=0; i<lc; i++){
        e1[i] = get_parent(e1[i]);
        e2[i] = get_parent(e2[i]);
        al1[e1[i]].push_back(e2[i]);
        al2[e2[i]].push_back(e1[i]);
    }
    memset(dp1, -1, m*sizeof(int));
    memset(dp2, -1, m*sizeof(int));
    for(int i=0; i<m; i++){
        if(p[i] != i) continue;
        if(!al2[i].size()){
            dfs1(i);
        }
        if(!al1[i].size()){
            dfs2(i);
        }
    }
    for(int ii=0; ii<m; ii++){
        int i = get_parent(ii);
        if(dp1[i] + dp2[i] == n-1){
            cout << 'K' << dp2[i]+1 << '\n';
        }
        else{
            cout << '?' << '\n';
        }
    }
    return 0;
}

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