oj.uz

Submission #251499

# Submission time Handle Problem Language Result Execution time Memory
251499 2020-07-21T13:53:48 Z apostoldaniel854 Pictionary (COCI18_pictionary) C++14
126 / 140
 1500 ms 10232 KB 
#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];
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 (rand () % 2) swap (x, y);
        gr[x].pb ({y, cost});
        gr[y].pb ({x, cost});
        f[y] = x;
    }
}

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;
    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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2832 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2944 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3620 KB Output is correct
2 Correct 36 ms 3580 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 4184 KB Output is correct
2 Correct 42 ms 3832 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 4776 KB Output is correct
2 Correct 59 ms 4728 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 5368 KB Output is correct
2 Correct 514 ms 5964 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 6392 KB Output is correct
2 Correct 101 ms 6264 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1552 ms 8356 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 8696 KB Output is correct
2 Correct 391 ms 9336 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 10232 KB Output is correct
2 Correct 460 ms 10104 KB Output is correct