Submission #768362

#	Time	Username	Problem	Language	Result	Execution time	Memory
768362		kojac	Pictionary (COCI18_pictionary)	C++17	140 / 140	36 ms	3156 KiB

pictionary

#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 / 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