Submission #636113

#	Time	Username	Problem	Language	Result	Execution time	Memory
636113		Cr45hor	Pictionary (COCI18_pictionary)	C++14	140 / 140	99 ms	23512 KiB

pictionary

#include <iostream>
#include <vector>
#include <algorithm>

#define Rep(i, l, r) for (int i = (l); i <= (r); i++)
#define rRep(i, r, l) for (int i = (r); i >= (l); i--)
#define epb emplace_back
#define F first
#define S second

using namespace std;

typedef pair < int, int > ii;
typedef vector < ii > vii;

int const N = 1e5 + 5;

int n, m, q, ass[N];

int root(int x) {
    return (ass[x] < 0 ? x : ass[x] = root(ass[x]));
}

bool union_(int x, int y) {
    if ((x = root(x)) == (y = root(y)))
        return false;

    if (ass[x] > ass[y]) swap(x, y);
    ass[x] += ass[y];
    ass[y] = x;
    return true;
}

vii g[N];
int par[18][N], max_par[18][N], dep[N], log_;

int preDFS(int u, int p) {
    int sz = 1;

    for (auto e: g[u]) {
        int v = e.S, w = e.F;
        if (v != p) {
            dep[v] = dep[u] + 1;
            par[0][v] = u;
            max_par[0][v] = w;
            sz += preDFS(v, u);
        }
    }

    return sz;
}

void prepare() {
    int mx = 0;
    Rep(v, 1, n) if (!dep[v]) {
        par[0][v] = v;
        max_par[0][v] = 0;
        mx = max(mx, preDFS(v, v));
    }

    log_ = 31 - __builtin_clz(mx);
    Rep(k, 1, log_) Rep(v, 1, n) {
        par[k][v] = par[k - 1][par[k - 1][v]];
        max_par[k][v] = max(max_par[k - 1][v], max_par[k - 1][par[k - 1][v]]);
    }
}

int lca(int u, int v) {
    if (root(u) != root(v))
        return -1;

    int ans = 0;

    if (dep[u] < dep[v])
        swap(u, v);
    while(dep[u] > dep[v]) {
        int k = 31 - __builtin_clz(dep[u] - dep[v]);
        ans = max(ans, max_par[k][u]);
        u = par[k][u];
    }
    if (u == v)
        return ans;

    rRep(k, log_, 0) if (par[k][u] != par[k][v]) {
        ans = max({ans, max_par[k][u], max_par[k][v]});
        u = par[k][u];
        v = par[k][v];
    }
    return max({ans, max_par[0][u], max_par[0][v]});
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    vector < pair < ii, int > > edges;

    cin >> n >> m >> q;
    fill(ass + 1, ass + n + 1, -1);

    for (int i = 1; i <= m; i++) {
        // gcd(u, v) = m - i + 1
        int u = m - i + 1;
        for (int v = u * 2; v <= n; v += u) {
            int w = i;
            if (union_(u, v)) {
                edges.epb(make_pair(u, v), w);
                g[u].epb(w, v);
                g[v].epb(w, u);
            }
        }
    }

    prepare();

    while(q--) {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << '\n';
    }
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14