oj.uz

Submission #752755

# Submission time Handle Problem Language Result Execution time Memory
752755 2023-06-03T16:19:38 Z ThegeekKnight16 Pictionary (COCI18_pictionary) C++17
140 / 140
 57 ms 1996 KB 
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
vector<int> pai, sub, edge;

int find(int v) {return ((pai[v] == v) ? v : find(pai[v]));}
void une(int a, int b, int temp)
{
    a = find(a); b = find(b);
    if (a == b) return;
    if (sub[a] < sub[b]) swap(a, b);
    pai[b] = a;
    sub[a] += sub[b];
    edge[b] = temp;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, M, Q;
    cin >> N >> M >> Q;
    pai.resize(N+1); edge.resize(N+1); sub.resize(N+1);
    iota(pai.begin(), pai.end(), 0);
    fill(sub.begin(), sub.end(), 1);
    fill(edge.begin(), edge.end(), INF);
    for (int i = M; i >= 1; i--)
    {
        for (int k = 2; k*i <= N; k++) une(i, k*i, M - i + 1);
    }

    // for (int i = 1; i <= N; i++) cerr << "||" << i << " " << pai[i] << " " << edge[i] << '\n';


    while (Q--)
    {
        int X, Y;
        cin >> X >> Y;
        int dist = -1;
        while (X != Y)
        {
            if (sub[X] > sub[Y]) {dist = max(dist, edge[Y]); Y = pai[Y];}
            else {dist = max(dist, edge[X]); X = pai[X];}
        }
        cout << dist << '\n';
    }
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 596 KB Output is correct
2 Correct 15 ms 520 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 708 KB Output is correct
2 Correct 20 ms 596 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 776 KB Output is correct
2 Correct 15 ms 912 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 900 KB Output is correct
2 Correct 31 ms 852 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1160 KB Output is correct
2 Correct 28 ms 1024 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1328 KB Output is correct
2 Correct 38 ms 1552 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1744 KB Output is correct
2 Correct 36 ms 1868 KB Output is correct

Subtask #10
14.0 / 14.0

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