Submission #206512

#	Time	Username	Problem	Language	Result	Execution time	Memory
206512		StanCatalin	KOVANICE (COI15_kovanice)	C++14	100 / 100	606 ms	72156 KiB

kovanice

#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

ifstream in("omg.in");
ofstream out("omg.out");

const int dim = 1000005;

int n,m,v,parent[dim],rg[dim],a[dim],componenta[dim],d[dim],r[dim];
vector < pair<int,int> > muchii;
vector <int> vec[dim];
vector <int> revec[dim];

int Find(int p)
{
    if (p == parent[p])
    {
        return p;
    }
    parent[p] = Find(parent[p]);
    return parent[p];
}

void Union(int x,int y)
{
    int rx = Find(x);
    int ry = Find(y);
    if (rg[rx] > rg[ry])
    {
        parent[ry] = rx;
    }
    else if (rg[rx] < rg[ry])
    {
        parent[rx] = ry;
    }
    else
    {
        parent[ry] = rx;
        rg[rx]++;
    }
}

int DFS1(int nod)
{
    if (d[nod] != 0) return d[nod];
    for (auto v:vec[nod])
    {
        d[nod] = max(d[nod], DFS1(v));
    }
    return ++d[nod];
}

int DFS2(int nod)
{
    if (r[nod] != 0) return r[nod];
    for (auto v:revec[nod])
    {
        r[nod] = max(r[nod], DFS2(v));
    }
    return ++r[nod];
}


int main()
{
    cin >> n >> m >> v;
    for (int i=1; i<=m; i++) parent[i] = i, componenta[i] = i;
    for (int i=1; i<=v; i++)
    {
        char comp;
        int a,b;
        cin >> a >> comp >> b;
        if (comp == '=')
        {
            Union(a,b);
        }
        else
        {
            muchii.push_back({a,b});
        }
    }
    for (auto e:muchii)
    {
        vec[Find(e.first)].push_back(Find(e.second));
        revec[Find(e.second)].push_back(Find(e.first));
    }
    for (int i=1; i<=m; i++)
        DFS1(componenta[i]);
    for (int i=1; i<=m; i++)
        DFS2(componenta[i]);
    ///cout << d[1] << " " << d[2] << "\n";
    for (int i=1; i<=m; i++)
    {
        if (d[Find(i)] + r[Find(i)] == n+1)
        {
            cout << "K" << r[Find(i)] << "\n";
        }
        else cout << "?\n";
    }
    return 0;
}

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