oj.uz

Submission #752244

# Submission time Handle Problem Language Result Execution time Memory
752244 2023-06-02T15:05:55 Z sophiadamm Pictionary (COCI18_pictionary) C++17
140 / 140
 192 ms 3296 KB 
#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.0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 528 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 1060 KB Output is correct
2 Correct 114 ms 1100 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 1476 KB Output is correct
2 Correct 137 ms 1448 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 1548 KB Output is correct
2 Correct 74 ms 1376 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 1480 KB Output is correct
2 Correct 89 ms 1504 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 2060 KB Output is correct
2 Correct 78 ms 1600 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 2268 KB Output is correct
2 Correct 143 ms 2788 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 2764 KB Output is correct
2 Correct 164 ms 2884 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 3296 KB Output is correct
2 Correct 178 ms 3276 KB Output is correct