Submission #1256429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256429		dbence	Pictionary (COCI18_pictionary)	C++20	140 / 140	99 ms	28228 KiB

pictionary

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define len(x) (x).size()
#define lsb(x) (x) & (-x)
#define l(x) (x << 1) + 1
#define r(x) (x << 1) + 2
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

template <typename T>
void print(T t) {
    cout << t << "\n";
}

template <typename T, typename... Args>
void print(T t, Args ...args) {
    cout << t << " ";
    print(args...);
}

const int N = 2e5 + 1;
const int L = 20;
int n, m, q;

struct Graph {
    int ind[N];
    int dep[N];
    int par[N];
    int anc[N][L];
    vector <int> adj[N];
} g;

struct Dsu {
    int par[N];
    int cnt[N];
    int ind[N];

    int root(int u) {
        return u == par[u]? u: par[u] = root(par[u]);
    }
    void unite(int u, int v) {
        u = root(u);
        v = root(v);
        if (u == v) {
            return;
        }
        if (cnt[u] < cnt[v]) {
            swap(u, v);
        }
        cnt[u] += cnt[v];
        par[v] = u;
    }
} dsu;

void dfs(int u, int d = 0) {
    static int t = 0;
    g.dep[u] = d;
    g.anc[u][0] =
    g.par[u];
    for (int i = 1; i < L; ++i) {
        g.anc[u][i] =
        g.anc[g.anc[u][i - 1]][i - 1];
    }
    for (int v: g.adj[u]) {
        g.par[v] = u;
        dfs(v, d + 1);
    }
}

int lca(int u, int v) {
    if (g.dep[u] < g.dep[v]) {
        swap(u, v);
    }
    int k = g.dep[u] - g.dep[v];
    for (int i = 0; i < L; ++i) {
        if (k >> i & 1) {
            u = g.anc[u][i];
        }
    }
    if (u == v) {
        return u;
    }
    for (int i = L - 1; i >= 0; --i) {
        if (g.anc[u][i] != g.anc[v][i]) {
            u = g.anc[u][i];
            v = g.anc[v][i];
        }
    }
    return g.par[u];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i <= n; ++i) {
        dsu.cnt[i] = 1;
        dsu.par[i] = i;
        dsu.ind[i] = i;
    }
    int on = n;
    for (int i = m; i >= 1; --i) {
        for (int j = i; j <= on; j += i) {
            if (dsu.root(i) != dsu.root(j)) {
                ++n;
                int u = dsu.ind[dsu.root(i)];
                int v = dsu.ind[dsu.root(j)];
                g.adj[n].pb(u);
                g.adj[n].pb(v);
                g.ind[n] = i;
                dsu.unite(i, j);
                dsu.ind[dsu.root(i)] = n;
            }
        }
    }
    dfs(n);
    for (int i = 0; i < q; ++i) {
        int u, v;
        cin >> u >> v;
        cout << m - g.ind[lca(u, v)] + 1 << "\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