Submission #757071

#	Time	Username	Problem	Language	Result	Execution time	Memory
757071		teesla	Pictionary (COCI18_pictionary)	C++14	140 / 140	49 ms	3188 KiB

pictionary

#include <bits/stdc++.h>
using namespace std;

struct dsu{

    vector<int> pai, rank, tempo;
    int n,t;

    dsu(int a){
        pai.assign(a,-1); rank.assign(a,0); tempo.assign(a,1e6);
        n = a;
        t=0;
    }

    int find(int a){
        if(pai[a] == -1) return a;
        return find(pai[a]);
    }

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

        if(rank[a] > rank[b]){pai[b] = a; tempo[b] = t;}
        else if(rank[b] > rank[a]){pai[a] = b; tempo[a] = t;}
        else{pai[b] = a; rank[a]++; tempo[b] = t;}
        return;
    }

    int query(int a, int b){
        int res = 0;

        while(a != b){
            if(tempo[a] < tempo[b]){res = max(res,tempo[a]); a = pai[a];}
            else {res = max(res,tempo[b]); b = pai[b];}

            if(a == b)return res;
        }
        return res;
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m,q; cin >> n >> m >> q;
    dsu v(n);

    for(int i=m; i>=1; i--){

        v.t++;
        for(int j = i+i; j<=n; j+=i) v.join(i-1, j-1);
    }

    while(q--){
        int a,b; cin >> a >> b;
        a--; b--;
        cout << v.query(a,b) << '\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