oj.uz

Submission #846194

# Submission time Handle Problem Language Result Execution time Memory
846194 2023-09-07T12:20:08 Z vjudge1 KOVANICE (COI15_kovanice) C++17
100 / 100
 260 ms 61268 KB 
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#define int long long
#define pb push_back
#define lim 300000
#define till 40001
// # of primes till 1e6 = 7e4
using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
using pii = array<int,2>;

const int mod=1000000007ll;

unordered_set<int>down[300000];
int depth[300000];
bool sure[300000],vis[300000];

int parent[300000];
int find(int i){
    if(parent[i]==i)return i;
    return parent[i]=find(parent[i]);
}
void unite(int i,int j){
    int x=find(i),y=find(j);
    parent[max(x,y)]=min(x,y);
}

struct query{
    int x,y;
    char c;
};

int dfs1(int a){
    //cerr<<a<<" is\n";
    if(!down[a].size()){
        //cerr<<"didnt "<<a<<"\n";
        return 1;
    }
    if(vis[a]){
        //cerr<<"already "<<a<<"\n";
        return depth[a];
    }
    //cerr<<"doin "<<a<<"\n";
    vis[a]=1;
    int ans=0;
    for(int i:down[a]){
        ans=max(ans,dfs1(i));
    }
    //cerr<<a<<" "<<ans+1<<"\n";
    return depth[a]=ans+1;
}
void dfs2(int a){
    sure[a]=1;
    for(int i:down[a]){
        if(depth[i]==depth[a]-1&&!vis[i]){
            vis[i]=1;
            dfs2(i);
        }
    }
}

void solve(){
    int n,m,v;
    cin>>n>>m>>v;
    for(int i=0;i<m;i++){
        parent[i]=i;
        sure[i]=0;
        vis[i]=0;
    }
    query qs[v];
    for(int i=0;i<v;i++){
        cin>>qs[i].x>>qs[i].c>>qs[i].y;
        qs[i].x--,qs[i].y--;
    }
    for(int i=0;i<v;i++){
        if(qs[i].c=='='){
            unite(qs[i].x,qs[i].y);
        }
    }
    for(int i=0;i<v;i++){
        if(qs[i].c=='<'){
            down[find(qs[i].y)].insert(find(qs[i].x));
        }
        if(qs[i].c=='>'){
            down[find(qs[i].x)].insert(find(qs[i].y));
        }
    }
    for(int i=0;i<m;i++){
        depth[find(i)]=dfs1(find(i));
    }
    for(int i=0;i<m;i++)vis[i]=0;
    for(int i=0;i<m;i++){
        if(depth[find(i)]==n&&!vis[find(i)]){
            dfs2(find(i));
        }
        //cerr<<depth[find(i)]<<" ";
    }
    for(int i=0;i<m;i++){
        if(sure[find(i)]){
            cout<<"K"<<depth[find(i)]<<"\n";
        }else{
            cout<<"?\n";
        }
    }
    //cerr<<down[find(3)].size()<<"\n";
}


signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
#ifdef Local  
#ifndef INTERACTIVE
    freopen("in","r",stdin);
#endif
    freopen("out","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20056 KB Output is correct
2 Correct 5 ms 20060 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 31436 KB Output is correct
2 Correct 63 ms 31572 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 22364 KB Output is correct
2 Correct 19 ms 22816 KB Output is correct
3 Correct 23 ms 23580 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 48668 KB Output is correct
2 Correct 185 ms 48468 KB Output is correct
3 Correct 172 ms 48408 KB Output is correct
4 Correct 229 ms 58704 KB Output is correct
5 Correct 260 ms 61268 KB Output is correct