oj.uz

Submission #714157

# Submission time Handle Problem Language Result Execution time Memory
714157 2023-03-24T03:38:53 Z ThiagoSDQ Pictionary (COCI18_pictionary) C++14
140 / 140
 67 ms 3284 KB 
#include <bits/stdc++.h>

#define mp make_pair
#define fi first
#define se second

using namespace std;

int n, m, q;
int anc[100010];
int tim[100010];
int w[100010];

int find(int x, int t){
    if(anc[x] == x) return x;
    if(tim[x] > t) return x;

    return find(anc[x], t);
}

void join(int x, int y, int t){
    x = find(x, t);
    y = find(y, t);
  
    if(x == y) return;

    if(w[x] < w[y]) swap(x, y);

    w[x] += w[y];
    anc[y] = x;
    tim[y] = t;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m >> q;

    for(int i=1; i<=n; i++){
        anc[i] = i;
        w[i] = 1;
    }

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

    for(int i=0; i<q; i++){
        int a, b;
        cin >> a >> b;

        int l = 1, r = m;

        while(l < r){
            int mid = (l+r)/2;

            if(find(a, mid) == find(b, mid)){
                r = mid;
            } else {
                l = mid+1;
            }
        }

        cout << r << "\n";
    }
}

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 6 ms 456 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1104 KB Output is correct
2 Correct 21 ms 1120 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1580 KB Output is correct
2 Correct 29 ms 1400 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1340 KB Output is correct
2 Correct 21 ms 1288 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1484 KB Output is correct
2 Correct 25 ms 1520 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1992 KB Output is correct
2 Correct 26 ms 1672 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2300 KB Output is correct
2 Correct 47 ms 2572 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 2916 KB Output is correct
2 Correct 55 ms 2888 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 3284 KB Output is correct
2 Correct 60 ms 3284 KB Output is correct