Submission #746508

#	Time	Username	Problem	Language	Result	Execution time	Memory
746508		hyakup	Pictionary (COCI18_pictionary)	C++17	140 / 140	215 ms	3064 KiB

pictionary

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
const int inf = 1e9;
int pai[maxn], peso[maxn], h[maxn];
int n, m, q; 

void init( int n ){ for( int i = 0; i <= n; i++ ) pai[i] = i, peso[i] = inf; }
int find( int a ){ return ( a == pai[a] ) ? a : find( pai[a] ); }
void join( int a, int b, int id ){
    a = find(a), b = find(b);
    if( a == b ) return;
    if( h[a] < h[b] + 1 ) swap( a, b );
    pai[b] = a; peso[b] = id;
    h[a] = max( h[a], h[b] + 1 );
}

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

int query( int a, int b ){
    int resp = 0;
    while( a != b ){
        if( peso[a] < peso[b] ) resp = max( resp,  peso[a] ), a = pai[a];
        else resp = max( resp, peso[b] ), b = pai[b];
    }
    return resp;
}

int main(){
    cin >> n >> m >> q;
    init(n);
    for( int i = 1; i <= m; i++ ) solve(i);
    while( q-- ){
        int a, b; cin >> a >> b;
        cout << query( a, b ) << 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