oj.uz

Submission #734675

# Submission time Handle Problem Language Result Execution time Memory
734675 2023-05-02T19:24:28 Z ETheBest3 KOVANICE (COI15_kovanice) C++17
50 / 100
 2000 ms 25336 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];
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++){
        if(in[find_parent(i)]==0)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

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

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 17084 KB Output is correct
2 Correct 61 ms 17228 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2069 ms 10148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2055 ms 25336 KB Time limit exceeded
2 Halted 0 ms 0 KB -