oj.uz

Submission #522720

# Submission time Handle Problem Language Result Execution time Memory
522720 2022-02-05T14:33:47 Z FronPaw KOVANICE (COI15_kovanice) C++14
50 / 100
 361 ms 36060 KB 
#include <bits/stdc++.h>
using namespace std;
int lg, n, m;
int unde[300001];
struct T
{
    int nr1, nr2;
    char cmp;
};
T op[300001];
int tata[300001], rang[300001];
int in[300001], in1[300001];
vector <int> v[300001];
vector <int> trans[300001];
bool viz[300001];
int ans[300001];
int find_tata (int nod)
{
    int rez = nod;
    while (nod != tata[nod])
        nod = tata[nod];
    while (rez != nod)
    {
        int cop = tata[rez];
        tata[rez] = nod;
        rez = cop;
    }
    return nod;
}
void uneste (int a, int b)
{
    if (rang[a] > rang[b])
        tata[b] = a;
    else
    {
        tata[a] = b;
        if (rang[a] == rang[b])
            rang[a]++;
    }
}
int viz1[300001];
int value[300001];
void dfs (int nod)
{
    value[nod] = 1;
    queue <int> q;
    q.push(nod);
    while (!q.empty())
    {
        int start = q.front();
        q.pop();
        for (auto vecin:trans[start])
            if (!viz1[vecin])
            {
                value[vecin] = value[start] + 1;
                q.push(vecin);
                viz1[vecin] = 1;
            }
    }
}
void dfs1 (int nod, int dist)
{
    viz1[nod] = 1;
    if (value[nod] + dist == lg)
        ans[nod] = value[nod];
    for (auto vecin:v[nod])
        if (!viz1[vecin])
            dfs1(vecin, dist + 1);
}
void solve ()
{
    for (int i = 1; i<=n; ++i)
        if (in1[unde[i]] == 0 && viz[unde[i]] == 0)
        {
            dfs(unde[i]);
            viz[unde[i]] = 1;
        }
    for (int i = 1;i<=n;++i)
        viz[i] = 0, viz1[i] = 0, ans[i] = -1;
    for (int i = 1;i<=n;++i)
        if (in[unde[i]] == 0 && viz[unde[i]] == 0 && value[unde[i]] == lg)
        {
            dfs1(unde[i], 0);
            viz[unde[i]] = 1;
        }
    return ;
}
int main ()
{
    cin >> lg >> n >> m;
    for (int i = 1; i<=m; ++i)
    {
        int a, b;
        char c;
        cin >> a >> c >> b;
        op[i].nr1 = a;
        op[i].nr2 = b;
        op[i].cmp = c;
    }
    for (int i = 1; i<=n; ++i)
        tata[i] = i;
    for (int i = 1; i<=m; ++i)
        if (op[i].cmp == '=')
            uneste(find_tata(op[i].nr1), find_tata(op[i].nr2));
    for (int i = 1; i<=n; ++i)
        unde[i] = find_tata(i);
    // use unde[nod] instead of nod
    for (int i = 1; i<=m; ++i)
        if (op[i].cmp == '<')
        {
            v[unde[op[i].nr2]].push_back(unde[op[i].nr1]);
            in[unde[op[i].nr1]]++;
            trans[unde[op[i].nr1]].push_back(unde[op[i].nr2]);
            in1[unde[op[i].nr2]]++;
        }
        else if (op[i].cmp == '>')
        {
            v[unde[op[i].nr1]].push_back(unde[op[i].nr2]);
            in[unde[op[i].nr2]]++;
            trans[unde[op[i].nr2]].push_back(unde[op[i].nr1]);
            in1[unde[op[i].nr1]]++;
        }
    solve();

    for (int i = 1;i<=n;++i)
        if (ans[unde[i]] == -1)
            cout << "?\n";
        else
            cout << "K" << ans[unde[i]] << '\n';
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14528 KB Output is correct
2 Correct 9 ms 14540 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 25652 KB Output is correct
2 Correct 142 ms 26176 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 40.0

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