oj.uz

Submission #576919

# Submission time Handle Problem Language Result Execution time Memory
576919 2022-06-13T19:20:46 Z PagodePaiva Pictionary (COCI18_pictionary) C++14
140 / 140
 57 ms 3728 KB 
#include<bits/stdc++.h>
#define ms(v) memset(v, -1, sizeof v)
#define pb push_back
#define mp make_pair
#define N 200010
using namespace std;

int n, m, q;
int pai[N], edge[N], sz[N], lvl[N];

void init(int x){
    pai[x] = x;
    sz[x] = 1;
}

int find(int x){
    return (x == pai[x] ? x : find(pai[x]));
}

void join(int a, int b, int d){
    a = find(a);
    b = find(b);

    if(a == b) return;

    if(sz[a] < sz[b]) swap(a, b);

    pai[b] = a;
    sz[a] += sz[b];
    edge[b] = d;  

    return;
}

int lca(int a){
    return lvl[a] = (a == pai[a] ? 0 : lca(pai[a]) + 1);
}

int dfs(int a, int b){
    if(find(a) != find(b)) return -1;

    int resa = 0, resb = 0;

    if(lvl[a] < lvl[b]) swap(a, b);

    while(lvl[a] > lvl[b]){
        if(resa < edge[a]) resa = edge[a];
        a = pai[a];
    }

    while(a != b){
        if(resa < edge[a]) resa = edge[a];
        if(resb < edge[b]) resb = edge[b];

        a = pai[a];
        b = pai[b];
    }

    return max(resa, resb);
}

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

    cin >> n >> m >>  q;

    for(int i = 1;i <= n;i++){
        init(i);
    }

    for (int i = m; i >= 1; i--)
        for (int j = i; j <= n; j += i) 
            join(j, i, m-i+1);

    for(int i = 1;i <= n;i++) lca(i);

    for(int i = 1;i <= q;i++){
        int a, b;
        cin >> a >> b;
        cout << dfs(a, b) << "\n";
    }

    return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1576 KB Output is correct
2 Correct 20 ms 1356 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1468 KB Output is correct
2 Correct 15 ms 1368 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1740 KB Output is correct
2 Correct 16 ms 1620 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2252 KB Output is correct
2 Correct 21 ms 1856 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2540 KB Output is correct
2 Correct 32 ms 2836 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3100 KB Output is correct
2 Correct 38 ms 3228 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 3728 KB Output is correct
2 Correct 41 ms 3696 KB Output is correct