oj.uz

답안 #907594

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
907594 2024-01-15T22:25:09 Z vjudge1 드문 곤충 (IOI22_insects) C++17
0 / 100
 1209 ms 2624 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;
    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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 106 ms 1384 KB Output is correct
8 Correct 20 ms 880 KB Output is correct
9 Correct 20 ms 1116 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 24 ms 968 KB Output is correct
12 Correct 6 ms 596 KB Output is correct
13 Correct 19 ms 600 KB Output is correct
14 Correct 6 ms 856 KB Output is correct
15 Correct 9 ms 856 KB Output is correct
16 Correct 11 ms 600 KB Output is correct
17 Correct 14 ms 868 KB Output is correct
18 Incorrect 16 ms 856 KB Wrong answer.
19 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 106 ms 1384 KB Output is correct
8 Correct 20 ms 880 KB Output is correct
9 Correct 20 ms 1116 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 24 ms 968 KB Output is correct
12 Correct 6 ms 596 KB Output is correct
13 Correct 19 ms 600 KB Output is correct
14 Correct 6 ms 856 KB Output is correct
15 Correct 9 ms 856 KB Output is correct
16 Correct 11 ms 600 KB Output is correct
17 Correct 14 ms 868 KB Output is correct
18 Incorrect 16 ms 856 KB Wrong answer.
19 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 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 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 16 ms 980 KB Output is correct
8 Incorrect 1209 ms 2624 KB Too many queries.
9 Halted 0 ms 0 KB -