Submission #251500

#	Time	Username	Problem	Language	Result	Execution time	Memory
251500		apostoldaniel854	Pictionary (COCI18_pictionary)	C++14	126 / 140	1596 ms	9372 KiB

pictionary

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

const int N = 1e5;
int c[1 + N], f[1 + N], p[1 + N], h[1 + N], sz[1 + N];
vector <pair <int, int>> gr[1 + N];

int ft (int x) {
    return (f[x] == x) ? x : f[x] = ft (f[x]);
}

void unite (int x, int y, int cost) {
    x = ft (x); y = ft (y);
    if (x != y) {
        if (sz[x] > sz[y]) swap (x, y);
        gr[x].pb ({y, cost});
        gr[y].pb ({x, cost});
        f[y] = x;
        sz[x] += sz[y];
    }
}

void dfs (int node, int par) {
    p[node] = par;
    h[node] = h[par] + 1;
    for (pair <int, int> edge : gr[node])
        if (edge.first != par) {
            dfs (edge.first, node);
            c[edge.first] = edge.second;
        }
}

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

    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        f[i] = i, sz[i] = 1;
    for (int i = m; i > 0; i--)
		for (int j = i; j <= n; j += i)
			unite (j, i, m  -i + 1);

    dfs (1, 0);
    while (q--) {
        int x, y;
        cin >> x >> y;
        int ans = 0;
        while (x != y) {
            if (h[x] > h[y]) {
                ans = max (ans, c[x]);
                x = p[x];
            }
            else {
                ans = max (ans, c[y]);
                y = p[y];
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

• 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: 0 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14