Submission #734679

#	Time	Username	Problem	Language	Result	Execution time	Memory
734679		ETheBest3	KOVANICE (COI15_kovanice)	C++14	100 / 100	206 ms	41740 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], maxdep[MAXN];
char vh2[MAXN];
vector<lli> v[MAXN];
bool used[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 dfs1(lli vr){
    if(maxdep[vr]!=0)return maxdep[vr];
    if(v[vr].size()==0){
        maxdep[vr]=1;
        return maxdep[vr];
    }
    maxdep[vr]=1;
    for(lli i=0; i<v[vr].size(); i++){
        maxdep[vr]=max(maxdep[vr], dfs1(v[vr][i])+1);
    }
    return maxdep[vr];
}
void dfs2(lli vr){
    if(used[vr])return;
    used[vr]=1;
    ans[vr]=maxdep[vr];
    for(lli i=0; i<v[vr].size(); i++){
        if(maxdep[v[vr][i]]==maxdep[vr]-1)dfs2(v[vr][i]);
    }
    return;
}
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(vh3[i])].push_back(find_parent(vh1[i]));
            in[find_parent(vh1[i])]++;
        }
    }
    for(lli i=1; i<=M; i++){
        if(in[find_parent(i)]==0)dfs1(find_parent(i));
    }
    for(lli i=1; i<=M; i++){
        if(in[find_parent(i)]==0 and maxdep[find_parent(i)]==N)dfs2(find_parent(i));
    }
    for(lli i=1; i<=M; i++){
        if(ans[find_parent(i)]==0)cout<<"?"<<endl;
        else cout<<"K"<<ans[find_parent(i)]<<endl;
    }
    return 0;
}

Compilation message (stderr)

kovanice.cpp: In function 'long long int dfs1(long long int)':
kovanice.cpp:38: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]
   38 |     for(lli i=0; i<v[vr].size(); i++){
      |                  ~^~~~~~~~~~~~~
kovanice.cpp: In function 'void dfs2(long long int)':
kovanice.cpp:47: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]
   47 |     for(lli i=0; i<v[vr].size(); i++){
      |                  ~^~~~~~~~~~~~~

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