Submission #1084430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084430		vjudge1	KOVANICE (COI15_kovanice)	C++14	0 / 100	2102 ms	19176 KiB

kovanice

#include <bits/stdc++.h>

using namespace std;
int n,m,v;
const int MAX=3*1e5+10;
int parent[MAX];
vector<int> graph[MAX];
int Find(int x)
{
    if(parent[x]==x)return x;
    else return parent[x]=Find(parent[x]);
}
void Unite(int x, int y)
{
    x=Find(x);
    y=Find(y);
    parent[y]=x;
}
int det[MAX];
void dfs(int node, int step)
{
    det[node]=step;
    for(auto x:graph[node])dfs(x,step+1);
}
int main()
{
    cin>>n>>m>>v;
    for(int i=0; i<m; i++)parent[i]=i;
    vector<pair<int,int> > op;
    bool ind[m];
    memset(det,-1,sizeof(det));
    memset(ind,false,sizeof(ind));
    for(int i=0; i<v; i++)
    {
        int a;
        cin>>a;
        char c;
        cin>>c;
        int b;
        cin>>b;
        a--;b--;
        if(c=='=')
        {
            op.push_back({a,b});
        }
        else
        {
            graph[a].push_back(b);
            ind[b]=true;
        }
    }
    for(int i=0; i<m; i++)
    {
        if(!ind[i] && graph[i].size()>0)
        {
            dfs(i,1);
            break;
        }
    }

    for(auto curr:op)
    {
        int a=Find(curr.first),b=Find(curr.second);
        if(ind[b] || graph[b].size())swap(a,b);
        Unite(a,b);
    }
    for(int i=0; i<m; i++)
    {
        int tmp=Find(i);
        if(det[tmp]==-1)cout<<"?"<<endl;
        else
        cout<<"K"<<det[tmp]<<endl;
    }
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 10
• Subtask 4: 0 / 40