Submission #522687

#	Time	Username	Problem	Language	Result	Execution time	Memory
522687		FronPaw	KOVANICE (COI15_kovanice)	C++14	0 / 100	255 ms	23460 KiB

kovanice

#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]++;
    }
}
vector <int> ordine;
bool viz1[300001];
void dfs (int nod)
{
    viz1[nod] = 1;
    ordine.push_back(nod);
    for (auto vecin:v[nod])
        if (!viz1[vecin])
            dfs(vecin);
}
void solve ()
{
    queue <int> q ;
    for (int i = 1; i<=n; ++i)
        if (in[unde[i]] == 0 && viz[unde[i]] == 0)
        {
            dfs(unde[i]);
            viz[unde[i]] = 1;
            int rr = lg;
            if (ordine.size() == lg)
                for (auto j:ordine)
                    ans[j] = rr--;
            else
                for (auto j:ordine)
                    ans[j] = -1;
            ordine.clear();
        }
    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 (stderr)

kovanice.cpp: In function 'void solve()':
kovanice.cpp:59:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |             if (ordine.size() == lg)
      |                 ~~~~~~~~~~~~~~^~~~~

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