oj.uz

Submission #237571

# Submission time Handle Problem Language Result Execution time Memory
237571 2020-06-07T11:43:57 Z pajajara KOVANICE (COI15_kovanice) C++14
100 / 100
 1024 ms 44552 KB 
#include <bits/stdc++.h>
using namespace std;
const int MX=300005;
int n,m,v;
int comp[MX];
vector<int>g[MX];
void compose(int v,int c){
    comp[v]=c;
    for(int i:g[v])
        if(!comp[i])
            compose(i,c);
}
int d[MX],r[MX];
vector<int>gd[MX],gr[MX];
int dfsx(int v){
    if(d[v]) return d[v];
    for(int i:gd[v])
        d[v]=max(d[v],dfsx(i));
    return ++d[v];
}
int dfsy(int v){
    if(r[v]) return r[v];
    for(int i:gr[v])
        r[v]=max(r[v],dfsy(i));
    return ++r[v];
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>v;
    vector<pair<int,int>>edg;
    while(v--){
        int a,b;char c;
        cin>>a>>c>>b;
        if(c=='<')edg.push_back({a,b});
        else{
            g[a].push_back(b);g[b].push_back(a);
        }
    }
    for(int i=1;i<=m;i++)
        if(!comp[i])
            compose(i,i);
    for(auto i:edg){
        int x=i.first,y=i.second;
        gd[comp[x]].push_back(comp[y]);
        gr[comp[y]].push_back(comp[x]);
    }
    for(int i=1;i<=m;i++){
        dfsx(comp[i]);dfsy(comp[i]);
    }
    for(int i=1;i<=m;i++){
        if(d[comp[i]]+r[comp[i]]==n+1)cout<<"K"<<r[comp[i]]<<endl;
        else cout<<"?"<<endl;
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 21632 KB Output is correct
2 Correct 22 ms 21632 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 30708 KB Output is correct
2 Correct 491 ms 30920 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 24216 KB Output is correct
2 Correct 42 ms 24344 KB Output is correct
3 Correct 43 ms 24344 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 885 ms 43696 KB Output is correct
2 Correct 878 ms 43108 KB Output is correct
3 Correct 929 ms 42980 KB Output is correct
4 Correct 975 ms 44176 KB Output is correct
5 Correct 1024 ms 44552 KB Output is correct