Submission #466330

#	Time	Username	Problem	Language	Result	Execution time	Memory
466330		MOUF_MAHMALAT	KOVANICE (COI15_kovanice)	C++11	0 / 100	2089 ms	53720 KiB

kovanice

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