Submission #714157

#	Time	Username	Problem	Language	Result	Execution time	Memory
714157		ThiagoSDQ	Pictionary (COCI18_pictionary)	C++14	140 / 140	67 ms	3284 KiB

pictionary

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14