oj.uz

Submission #768362

# Submission time Handle Problem Language Result Execution time Memory
768362 2023-06-28T02:13:04 Z kojac Pictionary (COCI18_pictionary) C++17
140 / 140
 36 ms 3156 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pb push_back
#define endl "\n"

 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
const int MAXN = 3e5 + 10;


int n , m, q, pai[MAXN], peso[MAXN], sz[MAXN], k;
vector<pair<int,pii>> v;

int mdc(int a, int b){
    if(b == 0) return a;

    return mdc(b, a%b);
}

int find(int x){
    if(x == pai[x]) return x;

    k++;

    return find(pai[x]);
}

void join(int x, int y, int z){
    x = find(x);
    y = find(y);

    if(x == y) return;

    if(sz[x] < sz[y]){
        pai[x] = y;
        peso[x] = z;
    }else if(sz[y] < sz[x]){
        pai[y] = x;
        peso[y] = z;
    }else{
        pai[x] = y;
        peso[x] = z;
        sz[y]++;
    }
}

int main(){
  	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    // freopen("wormhole.in","r",stdin);
    // freopen("wormhole.out","w",stdout);

    cin >> n >> m >> q;

    for(int i = 1; i <= n; i++){
        pai[i] = i;
    }

    for(int i = m; i > 0; i--){
        for(int j = i; j <= n; j += i){
            join(i, j, m-i+1);
        }
    }

    for(int i = 0; i < q; i++){
        int x, y, a, b, ans = -1;

        cin >> x >> y;

        if(find(x) == find(y)){
            ans = 0;
            k = 0;
            find(x);
            a = k;

            k = 0;
            find(y);
            b = k;

            while(x != y){
                if(a > b){
                    ans = max(peso[x], ans);
                    x = pai[x];
                    a--;
                }else{
                    ans = max(peso[y], ans);
                    y = pai[y];
                    b--;
                }
            }

        }
        cout << ans << endl;
    }

    


    return 0;
}

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 468 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1124 KB Output is correct
2 Correct 12 ms 1108 KB Output is correct

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1236 KB Output is correct
2 Correct 13 ms 1236 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1492 KB Output is correct
2 Correct 13 ms 1396 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1924 KB Output is correct
2 Correct 18 ms 1580 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2132 KB Output is correct
2 Correct 27 ms 2388 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2772 KB Output is correct
2 Correct 31 ms 2636 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3156 KB Output is correct
2 Correct 35 ms 2944 KB Output is correct