Submission #1084301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084301		vjudge1	KOVANICE (COI15_kovanice)	C++17	100 / 100	175 ms	40960 KiB

kovanice

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define ar array

const int LOG = 20;
const int MOD = 1e9 + 7;
const int INF = 1e18;

const int N = 3e5 + 20;

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

void join(int a,int b){
   // cout<<a + 1<<" "<<b + 1<<'\n';
    a = find(a);
    b = find(b);
    p[a] = b;
}

int ind[N];
vector<vector<int> > G;
vector<int> g[N];
int in[N];
bitset<N> vis;

int A[N];
int k;
int dep[N];

int dfs1(int x){
    if(dep[x] != -1)return dep[x];
    dep[x] = 1;
    for(auto u: g[x]){
        dep[x] = max(dep[x], dfs1(u) + 1);
    }
    return dep[x];
}
void dfs2(int x,int d){
    if(A[x])return;
    A[x] = d;
    for(auto u: g[x]){
        if(dep[u] + 1 == dep[x]){
            if(!A[u])dfs2(u, d + 1);
        }
    }
}


signed main() {
    iota(p, p + N, 0);
    int  n, m;
    cin>>k>>n>>m;
    vector<ar<int, 2> > e;
    while(m--){
        int u, v;
        char c;
        cin>>u;
        c = getchar();
        cin>>v;
        --u, --v;
        //cout<<u<<" "<<c<<" "<<v<<'\n';
        if(c == '=')join(u, v);
        else if(c == '>')e.push_back({v, u});
        else e.push_back({u, v});
    }   
    for(auto [u, v]: e){
        u = find(u), v = find(v);
        //cout<<u<<" "<<v<<endl;
        in[v]++;
        g[u].push_back(v);
    }
    memset(dep, -1, sizeof dep);
    for(int i = 0;i < n;i++){
        if(!in[i] && !A[i] && i == find(i)){
            int mx = dfs1(i);
            if(mx == k)dfs2(i, 1);
        }
    }
    for(int i =0 ;i < n;i++){
        if(A[find(i)])cout<<"K"<<A[find(i)]<<'\n';
        else cout<<"?\n";
    }
}

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