Submission #1120821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120821		TahirAliyev	KOVANICE (COI15_kovanice)	C++17	10 / 100	183 ms	62148 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 = 1e6 + 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;
        scanf("%d", &a);
        char c = getchar();
        scanf("%d", &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);
    }
    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();
}

Compilation message (stderr)

kovanice.cpp: In function 'void solve()':
kovanice.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         scanf("%d", &a);
      |         ~~~~~^~~~~~~~~~
kovanice.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%d", &b);
      |         ~~~~~^~~~~~~~~~

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