Submission #672049

#	Time	Username	Problem	Language	Result	Execution time	Memory
672049		Ahmed57	KOVANICE (COI15_kovanice)	C++14	100 / 100	302 ms	40252 KiB

kovanice

#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 (stderr)

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 / 10
• Subtask 2: 40 / 40
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40