Submission #522700

#	Time	Username	Problem	Language	Result	Execution time	Memory
522700		FronPaw	KOVANICE (COI15_kovanice)	C++14	50 / 100	346 ms	35700 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];
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, int dist)
{
    viz1[nod] = 1;
    value[nod] = dist;
    for (auto vecin:trans[nod])
        if (!viz1[vecin])
            dfs(vecin, dist + 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], 1);
            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 / 10
• Subtask 2: 40 / 40
• Subtask 3: 0 / 10
• Subtask 4: 0 / 40