oj.uz

Submission #206512

# Submission time Handle Problem Language Result Execution time Memory
206512 2020-03-03T16:25:46 Z StanCatalin KOVANICE (COI15_kovanice) C++14
100 / 100
 606 ms 72156 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 47352 KB Output is correct
2 Correct 37 ms 47356 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 54896 KB Output is correct
2 Correct 196 ms 56176 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 49128 KB Output is correct
2 Correct 111 ms 49260 KB Output is correct
3 Correct 109 ms 49132 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 63588 KB Output is correct
2 Correct 510 ms 66788 KB Output is correct
3 Correct 513 ms 66600 KB Output is correct
4 Correct 579 ms 71392 KB Output is correct
5 Correct 606 ms 72156 KB Output is correct