oj.uz

Submission #907591

# Submission time Handle Problem Language Result Execution time Memory
907591 2024-01-15T22:20:10 Z vjudge1 Rarest Insects (IOI22_insects) C++17
10 / 100
 195 ms 512 KB 
#include "insects.h"

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include<bits/stdc++.h>
#include<math.h>
using namespace std;

typedef int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)

#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)

#define NN 2010
#define M 1000000007 // 998244353

//DSU
ll parent[NN], sz[NN];
ll find(ll a){ return a == parent[a] ? a : parent[a] = find(parent[a]); }
void merge(ll u, ll v) {
    u = find(u), v=find(v);
    if (u!=v) {
        if (sz[u]<sz[v]) swap(u, v);
        sz[u] += sz[v];
        parent[v] = u;
    }
}


int min_cardinality(int N) {
    F(i, 0, N) parent[i] = i, sz[i] = 1;

    F(i, 0, N) {
        move_inside(i);
        F(j, i+1, N) {
            move_inside(j);
            ll shit = press_button();
            if (shit == 2) merge(i, j); 
            move_outside(j);
        }
        move_outside(i);
    }
    ll ans = N;
    F(i, 0, N) ans = min(ans, sz[find(i)]);
    return ans;

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 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 1 ms 340 KB Output is correct
6 Correct 93 ms 344 KB Output is correct
7 Correct 99 ms 344 KB Output is correct
8 Correct 93 ms 344 KB Output is correct
9 Correct 96 ms 344 KB Output is correct
10 Correct 90 ms 344 KB Output is correct
11 Correct 92 ms 344 KB Output is correct
12 Correct 94 ms 344 KB Output is correct
13 Correct 92 ms 344 KB Output is correct
14 Correct 92 ms 344 KB Output is correct
15 Correct 76 ms 344 KB Output is correct
16 Correct 93 ms 344 KB Output is correct
17 Correct 107 ms 344 KB Output is correct
18 Correct 107 ms 344 KB Output is correct
19 Correct 106 ms 344 KB Output is correct
20 Correct 97 ms 344 KB Output is correct
21 Correct 100 ms 344 KB Output is correct
22 Correct 84 ms 512 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 1 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 1 ms 340 KB Output is correct
6 Correct 93 ms 344 KB Output is correct
7 Correct 99 ms 344 KB Output is correct
8 Correct 93 ms 344 KB Output is correct
9 Correct 96 ms 344 KB Output is correct
10 Correct 90 ms 344 KB Output is correct
11 Correct 92 ms 344 KB Output is correct
12 Correct 94 ms 344 KB Output is correct
13 Correct 92 ms 344 KB Output is correct
14 Correct 92 ms 344 KB Output is correct
15 Correct 76 ms 344 KB Output is correct
16 Correct 93 ms 344 KB Output is correct
17 Correct 107 ms 344 KB Output is correct
18 Correct 107 ms 344 KB Output is correct
19 Correct 106 ms 344 KB Output is correct
20 Correct 97 ms 344 KB Output is correct
21 Correct 100 ms 344 KB Output is correct
22 Correct 84 ms 512 KB Output is correct
23 Incorrect 181 ms 344 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 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Partially correct 0 ms 344 KB Output is partially correct
6 Partially correct 1 ms 344 KB Output is partially correct
7 Incorrect 195 ms 344 KB Too many queries.
8 Halted 0 ms 0 KB -