Submission #752244

#	Time	Username	Problem	Language	Result	Execution time	Memory
752244		sophiadamm	Pictionary (COCI18_pictionary)	C++17	140 / 140	192 ms	3296 KiB

pictionary

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
const int INF = 0x3f3f3f3f;
 
int p[MAXN], pp[MAXN], w[MAXN];
int n, m, q;
 
int find(int x){
    if(p[x]==x) return x;
    return find(p[x]); 
}
 
void join(int x, int y, int t){ 
    x=find(x);
    y=find(y);
    if(x==y) return;
    if(w[x] > w[y]) swap(x, y);
    p[x] = y;
    pp[x] = t;
    w[y] += w[x];
}

void solve( int id ){
    int k = m - id + 1;
    for( int i = 2*k; i <= n; i += k ) join(k, i, id );
}

int main(){
    ios_base::sync_with_stdio(false); cout.tie(NULL);
    cin >> n >> m >> q;
    for(int i = 1; i<=n; i++){
        p[i] = i;
        pp[i] = INF;
        w[i] = 1;
    }

    for(int i = 1; i<=m; i++) solve(i);
 
    for(int i = 0; i<q; i++){
        int a, b; cin >> a >> b;
        int res = 0;
        while(a != b){
            if(pp[a] > pp[b]) swap(a, b);
            res = max(res, pp[a]);
            a = p[a];
        }
        cout << res << endl;
    }
 
}

• 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