oj.uz

Submission #757071

# Submission time Handle Problem Language Result Execution time Memory
757071 2023-06-12T13:48:53 Z teesla Pictionary (COCI18_pictionary) C++14
140 / 140
 49 ms 3188 KB 
#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.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 340 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1092 KB Output is correct
2 Correct 22 ms 1036 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1444 KB Output is correct
2 Correct 22 ms 1340 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1364 KB Output is correct
2 Correct 16 ms 1236 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1492 KB Output is correct
2 Correct 18 ms 1492 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1940 KB Output is correct
2 Correct 20 ms 1688 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2260 KB Output is correct
2 Correct 38 ms 2500 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2772 KB Output is correct
2 Correct 41 ms 2944 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 3188 KB Output is correct
2 Correct 49 ms 3176 KB Output is correct