Submission #989111

#	Time	Username	Problem	Language	Result	Execution time	Memory
989111		LOLOLO	KOVANICE (COI15_kovanice)	C++17	100 / 100	97 ms	28100 KiB

kovanice

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (ll)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 3e5 + 10;

struct DSU{
    vector <int> p, sz;
    void ass(int n) {
        p.assign(n + 1, 0);
        sz.assign(n + 1, 1);
    }  

    int get(int a) {
        return p[a] ? get(p[a]) : a;
    }

    void unite(int a, int b) {
        a = get(a), b = get(b);
        if (a == b)
            return;

        if (sz[a] < sz[b])
            swap(a, b);

        sz[a] += sz[b];
        p[b] = a;
    }
} D;

vector <pair <int, int>> save;
vector <int> ed[N];

void dfs(int u, vector <int> &f) {
    if (f[u] != -1)
        return;

    f[u] = 1;
    for (auto x : ed[u]) {
        if (f[x] == -1)
            dfs(x, f);

        f[u] = max(f[u], f[x] + 1);
    }
}

int m;

vector <int> process(vector <pair <int, int>>& save) {
    for (int i = 1; i <= m; i++)
        ed[i].clear();

    vector <int> f(m + 1, -1);
    for (auto x : save) {
        ed[D.get(x.f)].pb(D.get(x.s));
    }

    for (int i = 1; i <= m; i++) {
        int t = D.get(i);
        if (f[t] == -1)
            dfs(t, f);
    }

    return f;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, v;
    cin >> n >> m >> v;

    D.ass(m + 1);

    for (int i = 0; i < v; i++) {
        int a, c;
        char b;
        cin >> a >> b >> c;
        if (b == '=') {
            D.unite(a, c);
            continue;
        }

        if (b == '>')
            swap(a, c);

        save.pb({a, c});
    }

    vector <int> f1 = process(save);
    for (auto &x : save)
        swap(x.s, x.f);

    vector <int> f2 = process(save);

    for (int i = 1; i <= m; i++) {
        int t = D.get(i);
        if (f1[t] + f2[t] == n + 1) {
            cout << "K" << f2[t] << '\n';
        } else {
            cout << "?\n";
        }
    }

    return 0;
} 

/*
5 4 3
1 4 2 1 2
3
2
1
*/ 

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