oj.uz

Submission #752750

# Submission time Handle Problem Language Result Execution time Memory
752750 2023-06-03T15:40:59 Z mariaclara Pictionary (COCI18_pictionary) C++17
140 / 140
 245 ms 3308 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 1e5+10;
typedef pair<int,int> pii;
#define mk make_pair
#define pb push_back
#define f first
#define s second
 
int n, m, q, day, t[MAXN], pai[MAXN], sz[MAXN], comp;
 
int find(int x) {
    if(pai[x]==x) return x;
    return find(pai[x]);
}
 
void merge(int x, int y, int Time) {
    x = find(x);
    y = find(y);
    if(x==y) return;
    if(sz[x]>sz[y]) swap(x,y);
    pai[x] = y;
    t[x] = Time;
    sz[y] += sz[x];
}
int main() {
    cin >> n >> m >> q;
 
    for(int i = 1; i <= n; i++)
        pai[i] = i, sz[i] = 1, t[i] = 1e9;
    
    while(m--) {
        day++;
        for(int i = 2*m+2; i <= n; i+=m+1)
            merge(m+1, i, day);
    }

    while(q--) {
        int a, b, resp = 0;
        cin >> a >> b;
        while(a!=b) {
            if(t[a]<t[b]) resp = t[a], a = pai[a];
            else resp = t[b], b = pai[b];
        }
        cout << resp <<"\n";
    }
}

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 33 ms 452 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 1072 KB Output is correct
2 Correct 116 ms 1040 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 1568 KB Output is correct
2 Correct 151 ms 1396 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 1220 KB Output is correct
2 Correct 92 ms 1288 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 1484 KB Output is correct
2 Correct 96 ms 1528 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 1996 KB Output is correct
2 Correct 92 ms 1560 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 2356 KB Output is correct
2 Correct 154 ms 2556 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 2796 KB Output is correct
2 Correct 181 ms 2920 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 3308 KB Output is correct
2 Correct 245 ms 3220 KB Output is correct