oj.uz

Submission #251501

# Submission time Handle Problem Language Result Execution time Memory
251501 2020-07-21T13:58:23 Z apostoldaniel854 Pictionary (COCI18_pictionary) C++14
126 / 140
 1500 ms 9336 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], 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 && not h[edge.first]) {
            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);
    for (int i = 1; i <= n; i++) {
        if (not h[i])
            dfs (i, 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 3 ms 2688 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2856 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3064 KB Output is correct
2 Correct 51 ms 2964 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 3192 KB Output is correct
2 Correct 46 ms 3064 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 4344 KB Output is correct
2 Correct 88 ms 4216 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 4856 KB Output is correct
2 Correct 879 ms 5724 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 5880 KB Output is correct
2 Correct 142 ms 5880 KB Output is correct

Subtask #8
0 / 14.0

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

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 7928 KB Output is correct
2 Correct 564 ms 8652 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 9336 KB Output is correct
2 Correct 666 ms 9080 KB Output is correct