oj.uz

Submission #206511

# Submission time Handle Problem Language Result Execution time Memory
206511 2020-03-03T16:18:50 Z StanCatalin KOVANICE (COI15_kovanice) C++14
10 / 100
 522 ms 30944 KB 
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

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

const int dim = 3e5;

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);
            componenta[a] = Find(a);
            componenta[b] = Find(b);
        }
        else
        {
            muchii.push_back({a,b});
        }
    }
    for (auto e:muchii)
    {
        vec[componenta[e.first]].push_back(componenta[e.second]);
        revec[componenta[e.second]].push_back(componenta[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[componenta[i]] + r[componenta[i]] == n+1)
        {
            cout << "K" << r[componenta[i]] << "\n";
        }
        else cout << "?\n";
    }
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 40.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 16464 KB Output is correct
2 Correct 85 ms 16232 KB Output is correct
3 Correct 89 ms 16364 KB Output is correct

Subtask #4
0 / 40.0

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