Submission #757058

#	Time	Username	Problem	Language	Result	Execution time	Memory
757058		teesla	Pictionary (COCI18_pictionary)	C++14	28 / 140	1579 ms	1492 KiB

pictionary

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

int gcd(int a, int b){
    
    if(a>b) swap(a,b);
    while(a!=1){
        b = b%a;
        if(b == 0) return a;
        if(a > b) swap(a,b);
    }
    return 1;
}

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 = -1;

        while(a != b){
            if(tempo[a] < tempo[b]){res = tempo[a]; a = pai[a];}
            else {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=1; i<=m; i++){
        v.t++;

        for(int a = 1; a<=n; a++) for(int b = a+1; b<=n; b++){

            if(gcd(a,b) != (m-i + 1)) continue;
            v.join(a-1, b-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: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14