oj.uz

Submission #1074387

# Submission time Handle Problem Language Result Execution time Memory
1074387 2024-08-25T10:12:56 Z Zicrus Rarest Insects (IOI22_insects) C++17
10 / 100
 162 ms 448 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++) {
            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 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 109 ms 344 KB Output is correct
7 Correct 129 ms 344 KB Output is correct
8 Correct 125 ms 344 KB Output is correct
9 Correct 162 ms 340 KB Output is correct
10 Correct 129 ms 344 KB Output is correct
11 Correct 143 ms 344 KB Output is correct
12 Correct 130 ms 344 KB Output is correct
13 Correct 136 ms 344 KB Output is correct
14 Correct 142 ms 344 KB Output is correct
15 Correct 144 ms 344 KB Output is correct
16 Correct 125 ms 344 KB Output is correct
17 Correct 123 ms 344 KB Output is correct
18 Correct 119 ms 344 KB Output is correct
19 Correct 97 ms 344 KB Output is correct
20 Correct 126 ms 344 KB Output is correct
21 Correct 149 ms 340 KB Output is correct
22 Correct 133 ms 344 KB Output is correct

Subtask #2
0 / 15.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 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 109 ms 344 KB Output is correct
7 Correct 129 ms 344 KB Output is correct
8 Correct 125 ms 344 KB Output is correct
9 Correct 162 ms 340 KB Output is correct
10 Correct 129 ms 344 KB Output is correct
11 Correct 143 ms 344 KB Output is correct
12 Correct 130 ms 344 KB Output is correct
13 Correct 136 ms 344 KB Output is correct
14 Correct 142 ms 344 KB Output is correct
15 Correct 144 ms 344 KB Output is correct
16 Correct 125 ms 344 KB Output is correct
17 Correct 123 ms 344 KB Output is correct
18 Correct 119 ms 344 KB Output is correct
19 Correct 97 ms 344 KB Output is correct
20 Correct 126 ms 344 KB Output is correct
21 Correct 149 ms 340 KB Output is correct
22 Correct 133 ms 344 KB Output is correct
23 Incorrect 143 ms 448 KB Too many queries.
24 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 Partially correct 0 ms 344 KB Output is partially correct
6 Partially correct 0 ms 344 KB Output is partially correct
7 Incorrect 127 ms 424 KB Too many queries.
8 Halted 0 ms 0 KB -