Submission #1317240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317240		AzeTurk810	KOVANICE (COI15_kovanice)	C++20	100 / 100	143 ms	37584 KiB

kovanice

/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <utility>
#include <vector>

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using namespace std;

#define ln '\n'
#define INFi 1e9
#define INFll 1e18

#ifdef ONPC
#include <algo.hpp>
#else
#define dbg(...)
#define dbg_out(...)
#endif

struct DSU {
    vector<int> par;
    int n, components;

    DSU(int _n) {
        n = _n;
        components = n;
        par.assign(n, -1);
    }

    int Find(int u) {
        if (par[u] < 0)
            return u;
        return par[u] = Find(par[u]);
    }

    bool Union(int u, int v) {
        u = Find(u);
        v = Find(v);
        if (u != v) {
            components--;
            if (par[u] > par[v]) {
                swap(u, v);
            }
            par[u] += par[v];
            par[v] = u;
            return true;
        } else {
            return false;
        }
    }
};

char solve() {
    int N, M, V;
    if (!(cin >> N >> M >> V))
        return 1;
    DSU t(M);
    vector<vector<int>> g(M), gr(M);
    for (int _ = 0; _ < V; _++) {
        int u;
        cin >> u;
        char c;
        cin >> c;
        int v;
        cin >> v;
        u--, v--;
        if (c == '=') {
            t.Union(u, v);
        } else {
            g[v].push_back(u);
            gr[u].push_back(v);
        }
    }
    vector<int> lvl(M, -1), ans(M, -1);
    function<void(int)> dfs = [&](int v) {
        if (g[v].size() == 0)
            lvl[v] = 1;
        if (lvl[v] != -1)
            return;
        for (auto u : g[v]) {
            dfs(u);
            lvl[v] = max(lvl[v], lvl[u] + 1);
        }
        // return 1;
    };
    vector<char> used(M, false);
    function<void(int)> dfs2 = [&](int v) {
        used[v] = true;
        ans[v] = lvl[v];
        dbg(v);
        for (auto u : g[v]) {
            if (used[u] || (lvl[u] != lvl[v] - 1))
                continue;
            dfs2(u);
        }
    };
    dbg(gr);
    dbg(g);
    for (int i = 0; i < M; i++) {
        if (t.Find(i) == i)
            continue;
        for (auto u : g[i]) {
            g[t.Find(i)].push_back(u);
            gr[u].push_back(t.Find(i));
        }
        for (auto u : gr[i]) {
            g[u].push_back(t.Find(i));
            gr[t.Find(i)].push_back(u);
        }
    }
    for (int i = 0; i < M; i++) {
        if (lvl[t.Find(i)] == -1 && gr[t.Find(i)].empty()) {
            dfs(t.Find(i));
            // lvl[i] = lvl[t.Find(i)];
        }
    }
    dbg(lvl);
    for (int i = 0; i < M; i++) {
        if (lvl[t.Find(i)] == N) {
            dfs2(t.Find(i));
        }
    }
    for (int i = 0; i < M; i++) {
        dbg(i);
        dbg(t.Find(i));
        ans[i] = ans[t.Find(i)];
    }
    for (int i = 0; i < M; i++) {
        assert(ans[i] <= N);
        if (ans[i] == -1) {
            cout << "?\n";
        } else {
            cout << "K" << ans[i] << "\n";
        }
    }
    dbg(gr);
    dbg(g);
    // dbg(used);
    return 0;
}

// Attack on titan<3

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int t = 1e9;
    // cin >> t;
    for (int cases = 0; cases < t; cases++) {
        if (solve())
            break;
#ifdef ONPC
        cerr << "__________\n";
#endif
    }
}
// Just Imaginary
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
*/

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