Submission #1120940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120940		vjudge1	KOVANICE (COI15_kovanice)	C++17	100 / 100	177 ms	32400 KiB

kovanice

#include <bits/stdc++.h>
 
#define int long long
#define ll long long
#define pii pair<ll, ll>
#define all(v) v.begin(), v.end()
using namespace std;
const int oo = 1e9 + 9;
const int MAX = 3e5 + 5;
 
int m, n, v;
 
int par[MAX];
void init(){
    memset(par, -1, sizeof(par));
}
int get(int a){
    if(par[a] < 0) return a;
    return par[a] = get(par[a]);
}
bool unite(int u, int v){
    u = get(u), v = get(v);
    if(u == v) return 0;
    if(-par[u] < -par[v]) swap(u, v);
    par[u] += par[v];
    par[v] = u;
    return 1;
}
vector<pii> E;
vector<int> g[MAX];
int dp[MAX];
int ans[MAX];
 
void dfs(int node){
    dp[node] = 1;
    for(int to : g[node]){
        if(to == node) continue;
        if(!dp[to]) dfs(to);
        dp[node] = max(dp[to] + 1, dp[node]);
        // assert(dp[node] <= m);
    }
}
 
void dfs(int node, int cur){
    ans[node] = (m - cur + 1);
    for(int to : g[node]){
        if(to == node) continue;
        if(ans[to] || dp[to] != cur - 1) continue;
        dfs(to, cur - 1);
    }
}
 
void solve(){
    cin >> m >> n >> v;
    init();
    for(int i = 1; i <= v; i++){
        int a, b;
        char c;
        cin >> a >> c >> b;
        if(c == '=') unite(a, b);
        else E.push_back({a, b});
    }
    for(auto &a : E){
        a.first = get(a.first);
        a.second = get(a.second);
        g[a.first].push_back(a.second);
    }
    for(int i = 1; i <= n; i++){
        if(par[i] < 0 && !dp[i]) dfs(i);
        assert(dp[i] <= m);
    }
    for(int i = 1; i <= n; i++){
        if(par[i] < 0 && dp[i] == m){
            dfs(i, m);
        }
    }
    for(int i = 1; i <= n; i++){
        if(ans[get(i)]) cout << "K" << ans[get(i)] << '\n';
        else cout << "?\n";
    }
}
 
signed main(){
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) solve();
}

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