oj.uz

Submission #466330

# Submission time Handle Problem Language Result Execution time Memory
466330 2021-08-18T16:29:56 Z MOUF_MAHMALAT KOVANICE (COI15_kovanice) C++11
0 / 100
 2000 ms 53720 KB 
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
using namespace std;
typedef int ll;
ll n,m,q,d[300009],p[300009];
ll a[300009][2];
char c[300009];
bool b[300009],is[300009];
vector<vector<ll> >v;
set<pair<ll,ll> >s;
vector<pair<ll,ll> >op;
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;
    p[y]=x;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>q;
    v.resize(m+1);
    for(ll i=1; i<=m; i++)
        p[i]=i;
    for(ll i=1; i<=q; i++)
    {
        cin>>a[i][0]>>c[i]>>a[i][1];
        if(c[i]!='=')
            continue;
        mrg(a[i][0],a[i][1]);
    }
    for(ll i=1; i<=q; i++)
    {
        if(c[i]=='=')
            continue;
        ll x=gp(a[i][0]);
        ll y=gp(a[i][1]);
        if(c[i]=='<')
        {
            b[y]=1;
            v[x].push_back(y);
        }
        else
        {
            b[x]=1;
            v[y].push_back(x);
        }
    }
    for(ll i=1; i<=m; i++)
        if(!b[i]&&p[i]==i)
            d[i]=1,s.insert({1,i});
    while(!s.empty())
    {
        ll x=s.begin()->second;
        s.erase(s.begin());
        if(d[x]==n)
            is[x]=1;
        op.push_back({-d[x],x});
        for(auto z:v[x])
            if(d[z]<d[x]+1)
            {
                s.erase({d[z],z});
                d[z]=d[x]+1;
                s.insert({d[z],z});
            }
    }
    sort(all(op));
    for(auto u:op)
    {
        for(auto z:v[u.second])
            is[u.second]|=is[z];
    }
    for(ll i=1;i<=m;i++)
    {
        ll x=gp(i);
        if(is[x])
            cout<<"k"<<d[x]<<endl;
        else cout<<"?"<<endl;
    }
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 40.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 40.0

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