oj.uz

Submission #459260

# Submission time Handle Problem Language Result Execution time Memory
459260 2021-08-08T11:14:20 Z MOUF_MAHMALAT KOVANICE (COI15_kovanice) C++11
50 / 100
 206 ms 19060 KB 
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
using namespace std;
typedef int ll;
ll n,m,k,a[300009],b[300009];
ll p[300009],sz[300009],d[300009];
vector<vector<ll> >v;
char c[300009];
bool is[300009],st[300009],vis[300009];
ll gp(ll z)
{
    if(p[z]==z)
        return z;
    return p[z]=gp(p[z]);
}
void mrg(ll x,ll y)
{
    x=gp(x),y=gp(y);
    if(x==y)
        return;
    if(sz[x]<sz[y])
        swap(x,y);
    p[y]=x,sz[x]+=sz[y];
}
void dfs(ll id,ll op)
{
    d[id]=op;
    for(auto z:v[id])
    {
        if(d[z]==0)
            dfs(z,op+1);
        else
            d[z]=max(d[z],op+1);
    }
}
void go(ll id,ll op)
{
    d[id]=max(d[id],op);
    op=d[id];
    vis[id]=1;
    if(d[id]==n&&v[id].empty())
        return void(is[id]=1);
    for(auto z:v[id])
    {
        if(vis[z]==0)
            go(z,op+1);
        is[id]|=is[z];
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k;
    v.resize(m+1);
    for(ll i=1; i<=m; i++)
        p[i]=i,sz[i]=1;
    for(ll i=1; i<=k; i++)
    {
        cin>>a[i]>>c[i]>>b[i];
        if(c[i]=='=')
            mrg(a[i],b[i]);
    }
    for(ll i=1; i<=k; i++)
    {
        if(c[i]=='=')
            continue;
        if(c[i]=='<')
            v[gp(a[i])].push_back(gp(b[i])),st[gp(b[i])]=1;
        else
            v[gp(b[i])].push_back(gp(a[i])),st[gp(a[i])]=1;
    }
    for(ll i=1; i<=m; i++)
        if(st[i]==0&&p[i]==i)
            dfs(i,1);
    for(ll i=1; i<=m; i++)
        if(st[i]==0&&p[i]==i)
            go(i,1);
    for(ll i=1; i<=m; i++)
    {
        if(is[gp(i)])
            cout<<"K"<<d[gp(i)];
        else
            cout<<"?";
        cout<<"\n";
    }
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 10632 KB Output is correct
2 Correct 74 ms 10708 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 1868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 206 ms 19060 KB Output isn't correct
2 Halted 0 ms 0 KB -