Submission #734674

#	Time	Username	Problem	Language	Result	Execution time	Memory
734674		ETheBest3	KOVANICE (COI15_kovanice)	C++14	50 / 100	2073 ms	30280 KiB

kovanice

#include<bits/stdc++.h>
#define lli long long
#define endl "\n"
using namespace std;
const lli MAXN=300005;
lli N, M, V, vh1[MAXN], vh3[MAXN], par[MAXN], sz[MAXN], ans[MAXN], in[MAXN];
char vh2[MAXN];
vector<lli> v[MAXN];
void add_node(lli x){
    par[x]=x;
    sz[x]=1;
    return;
}
lli find_parent(lli x){
    if(par[x]==x)return x;
    return par[x]=find_parent(par[x]);
}
void merge_v(lli x, lli y){
    lli rootx=find_parent(x), rooty=find_parent(y);
    if(sz[rootx]>=sz[rooty]){
        par[rooty]=rootx;
        sz[rootx]+=sz[rooty];
        return;
    }else{
        par[rootx]=rooty;
        sz[rooty]+=sz[rootx];
        return;
    }
}
lli dfs(lli vr, lli dep){
    if(v[vr].size()==0){
        if(dep==N)ans[vr]=dep;
        else if(ans[vr]==0)ans[vr]=-1;
        return dep;
    }
    bool fl=0;
    for(lli i=0; i<v[vr].size(); i++){
        if(dfs(v[vr][i], dep+1)==N)fl=1;
    }
    if(fl==1)ans[vr]=dep;
    else if(ans[vr]==0)ans[vr]=-1;
    if(fl==1)return N;
    return -1;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>M>>V;
    for(lli i=1; i<=M; i++)add_node(i);
    for(lli i=0; i<V; i++){
        cin>>vh1[i]>>vh2[i]>>vh3[i];
        if(vh2[i]=='=')merge_v(vh1[i], vh3[i]);
    }
    for(lli i=0; i<V; i++){
        if(vh2[i]=='<'){
            v[find_parent(vh1[i])].push_back(find_parent(vh3[i]));
            in[find_parent(vh3[i])]++;
        }
    }
    for(lli i=1; i<=M; i++){
        dfs(find_parent(i), 1);
    }
    for(lli i=1; i<=M; i++){
        if(ans[find_parent(i)]==-1)cout<<"?"<<endl;
        else cout<<"K"<<ans[find_parent(i)]<<endl;
    }
    return 0;
}

Compilation message (stderr)

kovanice.cpp: In function 'long long int dfs(long long int, long long int)':
kovanice.cpp:37:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(lli i=0; i<v[vr].size(); i++){
      |                  ~^~~~~~~~~~~~~

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