oj.uz

Submission #746508

# Submission time Handle Problem Language Result Execution time Memory
746508 2023-05-22T15:19:50 Z hyakup Pictionary (COCI18_pictionary) C++17
140 / 140
 215 ms 3064 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 340 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 448 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 1088 KB Output is correct
2 Correct 126 ms 1232 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 1500 KB Output is correct
2 Correct 147 ms 1332 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 1356 KB Output is correct
2 Correct 89 ms 1200 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 1432 KB Output is correct
2 Correct 97 ms 1376 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 1948 KB Output is correct
2 Correct 84 ms 1560 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 2064 KB Output is correct
2 Correct 160 ms 2432 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 2688 KB Output is correct
2 Correct 183 ms 2632 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 3064 KB Output is correct
2 Correct 215 ms 2908 KB Output is correct