oj.uz

Submission #1084301

# Submission time Handle Problem Language Result Execution time Memory
1084301 2024-09-05T19:02:50 Z vjudge1 KOVANICE (COI15_kovanice) C++17
100 / 100
 175 ms 40960 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19292 KB Output is correct
2 Correct 5 ms 17244 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 21836 KB Output is correct
2 Correct 56 ms 23240 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 21704 KB Output is correct
2 Correct 30 ms 22468 KB Output is correct
3 Correct 31 ms 22468 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 28116 KB Output is correct
2 Correct 153 ms 31672 KB Output is correct
3 Correct 146 ms 31572 KB Output is correct
4 Correct 167 ms 34428 KB Output is correct
5 Correct 175 ms 40960 KB Output is correct