Submission #1268939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268939		cerq	Pictionary (COCI18_pictionary)	C++20	140 / 140	83 ms	35652 KiB

pictionary

#include <bits/stdc++.h>
#define FOD(i, a, b) for (int i = a; i <= b; ++i)
#define fi first
#define se second
#define all(x) x.begin(), x.end()

using namespace std;

const int N = 3e6 + 1;
const int mod = 1e9 + 7;
const int inf = 1e9;

int par[N], h[N], acs[N][20];
int cnt, weight[N];
vector <int> adj[N];
int n, m, q;

int find_root(int u) {
    return(par[u] == u ? u : par[u] = find_root(par[u]));
}

void addEdge(int u, int v, int w) {
    u = find_root(u);
    v = find_root(v);

    if (u == v) return;
    cnt++;
    weight[cnt] = w;
    adj[cnt].push_back(u);
    adj[cnt].push_back(v);
    par[v] = par[u] = cnt;
}

void dfs(int u) {
    for (int v : adj[u]) {
        h[v] = h[u] + 1;
        acs[v][0] = u;
        dfs(v);
    }
}

int lca(int u, int v) {
    if (h[u] < h[v]) swap(u, v);

    int dec = h[u] - h[v];

    for (int i = 18; ~i; --i) {
        if ((dec >> i) & 1) u = acs[u][i];
    }

    if (u == v) return u;

    for (int i = 18; ~i; --i) {
        if (acs[u][i] != acs[v][i]) {
            u = acs[u][i];
            v = acs[v][i];
        }
    }

    return acs[u][0];
}

main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
  
    cin >> n >> m >> q;

    for (int i = 1; i < N; ++i) par[i] = i;

    cnt = n;
    for (int i = m; i >= 1; --i) {
        for (int j = i + i; j <= n; j += i) {
            addEdge(i, j, m - i + 1);
        }
    }

    dfs(cnt);

    for (int j = 1; j <= 18; ++j) {
        for (int i = 1; i <= cnt; ++i)
        acs[i][j] = acs[acs[i][j - 1]][j - 1];
    }

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

    return 0;
}

Compilation message (stderr)

pictionary.cpp:63:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   63 | main()
      | ^~~~

• 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