oj.uz

Submission #672049

# Submission time Handle Problem Language Result Execution time Memory
672049 2022-12-14T16:28:26 Z Ahmed57 KOVANICE (COI15_kovanice) C++14
100 / 100
 302 ms 40252 KB 
#include<bits/stdc++.h>
using namespace std;
//DSU
int mn = 300001;
int pr[300001];
int gs[300001];

int findleader(int x){
    if(pr[x]==x){
        return x;
    }
    return pr[x] = findleader(pr[x]);
}
void mergegroup(int x,int y){
    int led1 = findleader(x);
    int led2 = findleader(y);
    if(led1==led2)return;
    if(gs[led1]>gs[led2]){
        pr[led2]=led1;
        gs[led1]+=gs[led2];
    }else{
        pr[led1]=led2;
        gs[led2]+=gs[led1];
    }
}
vector<int> adj1[300001];
vector<int> adj2[300001];
long long dp1[300001];
long long dp2[300001];
long long solve1(int i){
    if(dp1[i]!=-1)return dp1[i];
    long long c1 = 0;
    for(auto j:adj1[i]){
        c1 = max(c1,solve1(j)+1);
    }
    return dp1[i] = c1;
}long long solve2(int i){
    if(dp2[i]!=-1)return dp2[i];
    long long c1 = 0;
    for(auto j:adj2[i]){
        c1 = max(c1,solve2(j)+1);
    }
    return dp2[i] = c1;
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m,v;
    cin>>n>>m>>v;
    for(int i = 0;i<mn;i++)pr[i]=i,gs[i]=1;
    vector<pair<int,int>> ed;
    memset(dp1,-1,sizeof dp1);
    memset(dp2,-1,sizeof dp2);
    for(int i = 0;i<v;i++){
        string s;cin>>s;
        bool ss = 0;
        long long a= 0,b = 0;
        char c;
        for(auto j:s){
            if(j=='='||j=='<'||j=='>'){
                c = j;
                ss = !ss;
            }else if(ss){
                a*=10;
                a+=(j-'0');
            }else {
                b*=10;
                b+=(j-'0');
            }
        }
        if(c=='='){
            mergegroup(a,b);
        }if(c=='<'){
            ed.push_back({a,b});
        }if(c=='>'){
            ed.push_back({b,a});
        }
    }
    for(auto i:ed){
        adj1[findleader(i.first)].push_back(findleader(i.second));
        adj2[findleader(i.second)].push_back(findleader(i.first));
    }
    for(int i = 1;i<=m;i++){
        long long a = solve1(findleader(i));
        long long b = solve2(findleader(i));
        if(a+b==n-1)cout<<"K"<<a+1<<"\n";
        else cout<<"?\n";
    }
}

Compilation message

kovanice.cpp: In function 'int main()':
kovanice.cpp:74:10: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |         }if(c=='>'){
      |          ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21460 KB Output is correct
2 Correct 12 ms 21460 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 26116 KB Output is correct
2 Correct 78 ms 26328 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24008 KB Output is correct
2 Correct 23 ms 24108 KB Output is correct
3 Correct 24 ms 24104 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 35588 KB Output is correct
2 Correct 210 ms 35004 KB Output is correct
3 Correct 220 ms 34800 KB Output is correct
4 Correct 263 ms 39520 KB Output is correct
5 Correct 302 ms 40252 KB Output is correct