oj.uz

Submission #734679

# Submission time Handle Problem Language Result Execution time Memory
734679 2023-05-02T19:39:10 Z ETheBest3 KOVANICE (COI15_kovanice) C++14
100 / 100
 206 ms 41740 KB 
#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

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.0 / 10.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 18820 KB Output is correct
2 Correct 84 ms 18928 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 10196 KB Output is correct
2 Correct 22 ms 11048 KB Output is correct
3 Correct 21 ms 11000 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 30028 KB Output is correct
2 Correct 183 ms 33680 KB Output is correct
3 Correct 191 ms 33560 KB Output is correct
4 Correct 180 ms 35020 KB Output is correct
5 Correct 206 ms 41740 KB Output is correct