Submission #237571

#	Time	Username	Problem	Language	Result	Execution time	Memory
237571		pajajara	KOVANICE (COI15_kovanice)	C++14	100 / 100	1024 ms	44552 KiB

kovanice

#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 / 10
• Subtask 2: 40 / 40
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40