oj.uz

Submission #1074389

# Submission time Handle Problem Language Result Execution time Memory
1074389 2024-08-25T10:14:11 Z Zicrus Rarest Insects (IOI22_insects) C++17
10 / 100
 152 ms 592 KB 
#include <bits/stdc++.h>
#include "insects.h"
using namespace std;

typedef long long ll;

int n;
vector<int> lnk, sz;

int find(int a) {
    if (lnk[a] != a) return lnk[a] = find(lnk[a]);
    return lnk[a];
}

void unite(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return;
    lnk[a] = b;
    sz[b] += sz[a];
}

int min_cardinality(int N) {
    n = N;
    lnk = vector<int>(n);
    sz = vector<int>(n, 1);
    for (int i = 0; i < n; i++) lnk[i] = i;

    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (find(i) == find(j)) continue;
            move_inside(i);
            move_inside(j);
            if (press_button() > 1) unite(i, j);
            move_outside(i);
            move_outside(j);
        }
    }

    int mn = n;
    for (int i = 0; i < n; i++) {
        if (i != lnk[i]) continue;
        mn = min(mn, sz[i]);
    }
    return mn;
}

#ifdef TEST
#include "grader.cpp"
#endif

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 148 ms 344 KB Output is correct
8 Correct 110 ms 344 KB Output is correct
9 Correct 118 ms 344 KB Output is correct
10 Correct 3 ms 344 KB Output is correct
11 Correct 92 ms 344 KB Output is correct
12 Correct 90 ms 344 KB Output is correct
13 Correct 110 ms 344 KB Output is correct
14 Correct 91 ms 344 KB Output is correct
15 Correct 130 ms 344 KB Output is correct
16 Correct 152 ms 344 KB Output is correct
17 Correct 98 ms 344 KB Output is correct
18 Correct 111 ms 344 KB Output is correct
19 Correct 94 ms 344 KB Output is correct
20 Correct 134 ms 344 KB Output is correct
21 Correct 138 ms 344 KB Output is correct
22 Correct 132 ms 344 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 148 ms 344 KB Output is correct
8 Correct 110 ms 344 KB Output is correct
9 Correct 118 ms 344 KB Output is correct
10 Correct 3 ms 344 KB Output is correct
11 Correct 92 ms 344 KB Output is correct
12 Correct 90 ms 344 KB Output is correct
13 Correct 110 ms 344 KB Output is correct
14 Correct 91 ms 344 KB Output is correct
15 Correct 130 ms 344 KB Output is correct
16 Correct 152 ms 344 KB Output is correct
17 Correct 98 ms 344 KB Output is correct
18 Correct 111 ms 344 KB Output is correct
19 Correct 94 ms 344 KB Output is correct
20 Correct 134 ms 344 KB Output is correct
21 Correct 138 ms 344 KB Output is correct
22 Correct 132 ms 344 KB Output is correct
23 Correct 5 ms 344 KB Output is correct
24 Incorrect 147 ms 344 KB Too many queries.
25 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Partially correct 1 ms 344 KB Output is partially correct
7 Correct 12 ms 592 KB Output is correct
8 Incorrect 130 ms 344 KB Too many queries.
9 Halted 0 ms 0 KB -