oj.uz

Submission #636113

# Submission time Handle Problem Language Result Execution time Memory
636113 2022-08-28T07:06:25 Z Cr45hor Pictionary (COCI18_pictionary) C++14
140 / 140
 99 ms 23512 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2948 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3648 KB Output is correct
2 Correct 20 ms 3732 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4048 KB Output is correct
2 Correct 25 ms 3972 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 7396 KB Output is correct
2 Correct 24 ms 7448 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 9120 KB Output is correct
2 Correct 29 ms 10292 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 12212 KB Output is correct
2 Correct 37 ms 12428 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 15620 KB Output is correct
2 Correct 62 ms 17408 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 19088 KB Output is correct
2 Correct 94 ms 21400 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 23412 KB Output is correct
2 Correct 99 ms 23512 KB Output is correct