oj.uz

Submission #907596

# Submission time Handle Problem Language Result Execution time Memory
907596 2024-01-15T22:26:11 Z vjudge1 Rarest Insects (IOI22_insects) C++17
10 / 100
 1202 ms 2452 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;
    }
}

vector<pair<pl, ll>> cache;

void query(ll i, ll j) {
    if (find(i) == find(j)) return;
    for (auto [hist, q]: cache) {
        auto [li, ri] = hist;
        if (find(li) == find(i) and find(ri) == find(j)) {
            // we already know the answer for this 
            if (q == 2) merge(i, j);
            return;
        }
    }
    // assume I is already moved in
    move_inside(j);
    ll shit = press_button();
    if (shit == 2) merge(i, j); 
    cache.emplace_back(pair(i, j), shit);
    move_outside(j);
}

void rec(ll l, ll r) {
    if (l + 1 >= r) return;
    ll m = (l+r)/2;
    rec(l, m); rec(m, r);
    F(i, l, m) {
        move_inside(i);
        F(j, m, r) {
            query(i, j);
        }
        move_outside(i);
    }
}

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

    rec(0, N);
    
    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 1 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 0 ms 344 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 389 ms 1900 KB Output is correct
8 Correct 42 ms 968 KB Output is correct
9 Correct 38 ms 1368 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 72 ms 948 KB Output is correct
12 Correct 9 ms 600 KB Output is correct
13 Correct 37 ms 856 KB Output is correct
14 Correct 11 ms 952 KB Output is correct
15 Correct 19 ms 856 KB Output is correct
16 Correct 25 ms 604 KB Output is correct
17 Correct 34 ms 1112 KB Output is correct
18 Correct 37 ms 1112 KB Output is correct
19 Correct 56 ms 1384 KB Output is correct
20 Correct 154 ms 1496 KB Output is correct
21 Correct 257 ms 2176 KB Output is correct
22 Correct 303 ms 1548 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 344 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 389 ms 1900 KB Output is correct
8 Correct 42 ms 968 KB Output is correct
9 Correct 38 ms 1368 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 72 ms 948 KB Output is correct
12 Correct 9 ms 600 KB Output is correct
13 Correct 37 ms 856 KB Output is correct
14 Correct 11 ms 952 KB Output is correct
15 Correct 19 ms 856 KB Output is correct
16 Correct 25 ms 604 KB Output is correct
17 Correct 34 ms 1112 KB Output is correct
18 Correct 37 ms 1112 KB Output is correct
19 Correct 56 ms 1384 KB Output is correct
20 Correct 154 ms 1496 KB Output is correct
21 Correct 257 ms 2176 KB Output is correct
22 Correct 303 ms 1548 KB Output is correct
23 Correct 9 ms 1104 KB Output is correct
24 Incorrect 1200 ms 2452 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 1 ms 344 KB Output is correct
3 Correct 0 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 1 ms 596 KB Output is correct
7 Partially correct 24 ms 864 KB Output is partially correct
8 Incorrect 1202 ms 1940 KB Too many queries.
9 Halted 0 ms 0 KB -