oj.uz

Submission #757067

# Submission time Handle Problem Language Result Execution time Memory
757067 2023-06-12T13:38:55 Z teesla Pictionary (COCI18_pictionary) C++14
28 / 140
 1500 ms 1492 KB 
#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 = 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=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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 368 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 590 ms 488 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1564 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1561 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1563 ms 596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1552 ms 724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1543 ms 852 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1562 ms 1100 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1576 ms 1236 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1564 ms 1492 KB Time limit exceeded
2 Halted 0 ms 0 KB -