oj.uz

Submission #522664

# Submission time Handle Problem Language Result Execution time Memory
522664 2022-02-05T11:11:14 Z FronPaw KOVANICE (COI15_kovanice) C++14
10 / 100
 266 ms 23112 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];
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]++;
    }
}
void solve ()
{
    queue <int> q ;
    vector <int> ordine;
    for (int i = 1; i<=n; ++i)
        if (in[unde[i]] == 0 && viz[unde[i]] == 0)
        {
            q.push(unde[i]);
            viz[unde[i]] = 1;
        }
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        ordine.push_back(u);

        for (auto vecin:v[u])
        {
            in[vecin] --;
            if (in[vecin] == 0)
                q.push(vecin);
        }
    }
    int current_sum = 1;
    for (int i = 1; i<ordine.size(); ++i)
    {
        if (in1[ordine[i]] == 0)
        {
            if (current_sum == lg)
                for (int j = i - 1, rr = 1; rr <= lg; --j, ++rr)
                    ans[ordine[j]] = rr;
            else
                for (int j = i - 1, rr = 1; rr <= current_sum ; --j, ++rr)
                    ans[ordine[j]] = -1;
            current_sum = 1;
        }
        else
            current_sum++;
    }
    if (current_sum == lg)
        for (int j = ordine.size() - 1, rr = 1; rr <= lg ; j--, ++rr)
            ans[ordine[j]] = rr;
    else
        for (int j = ordine.size() - 1, rr = 1; rr <= current_sum; j--, ++rr)
            ans[ordine[j]] = -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]]++;
            in1[unde[op[i].nr1]]++;
        }
        else if (op[i].cmp == '>')
        {
            v[unde[op[i].nr1]].push_back(unde[op[i].nr2]);
            in[unde[op[i].nr2]]++;
            in1[unde[op[i].nr2]]++;
        }
    solve();

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

Compilation message

kovanice.cpp: In function 'void solve()':
kovanice.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int i = 1; i<ordine.size(); ++i)
      |                     ~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 16060 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 47 ms 9076 KB Output is correct
2 Correct 49 ms 9944 KB Output is correct
3 Correct 52 ms 9908 KB Output is correct

Subtask #4
0 / 40.0

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