제출 #1319498

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319498		goshgar_468	KOVANICE (COI15_kovanice)	C++20	80 / 100	104 ms	30416 KiB

kovanice

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

# define int long long
# define QR ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
# define endl '\n'
# define all(x) x.begin(), x.end()
# define ff first
# define ss second
# define pb push_back

const int INF = 1e18;
const int sz = 3e5 + 5;

char c[sz];
vector<int> g[sz] , p(sz, -1) , dp(sz) , ans(sz);

int get(int x){
    if (p[x] < 0)
        return x;
    return p[x] = get(p[x]);
}

bool unite(int u, int v){
    u = get(u), v = get(v);
    if (u == v)
        return 0;
    if (p[u] > p[v])
        swap(u, v);
    p[u] += p[v], p[v] = u;
    return true;
}

void dfs(int v){
    dp[v] = 1;
    for (int i : g[v]){
        if (!dp[i])
            dfs(i);
        dp[v] = max(dp[v], dp[i] + 1);
    }
}

void dfs(int v, int dist){
    ans[v] = dist;
    for (int i : g[v]){
        if (dp[i] == dp[v] - 1 && !ans[i]){
            dfs(i, dist + 1);
        }
    }
}

void CASE() {
    int n, m, v;
    cin >> n >> m >> v;
    vector < int > a(m + 1), b(m + 1);
    for (int i = 1; i <= v; i++){
        cin >> a[i] >> c[i] >> b[i];
        if (c[i] == '='){
            unite(a[i], b[i]);
        }
    }
    for (int i = 1; i <= v; i++){
        if (c[i] == '<'){
            g[get(a[i])].pb(get(b[i]));
        }
    }
    for (int i = 1; i <= m; i++){
        if (p[get(i)] < 0 && !dp[get(i)]){
            dfs(get(i));
        }
    }
    for (int i = 1; i <= m; i++){
        if (dp[get(i)] == n && !ans[get(i)]){
            dfs(get(i), 1);
        }
    }
    for (int i = 1; i <= m; i++){
        if (ans[get(i)])
            cout << "K" << ans[get(i)];
        else
            cout << "?";
        cout << endl;
    }
}   

signed main() {
    QR;
    int TESTS = 1;
    // cin >> TESTS;
    for (int TEST = 1; TEST <= TESTS; TEST++) {
        // cout << "Case #TEST << ": " ;
        CASE();
    }
    return 0;
}

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