oj.uz

답안 #807267

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
807267 2023-08-04T15:22:50 Z YassirSalama 드문 곤충 (IOI22_insects) C++17
10 / 100
 188 ms 1072 KB 
#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define OVL(v,s) for(auto x:v) cout<<x<<s;cout<<endl;
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pb push_back
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define endl "\n"
#define mod 1000000007
const ll INF=1e18;
const int MAXN=1e5+100;
int par[MAXN];
int sz[MAXN];
void make_set(){
    for(int i=0;i<MAXN;i++) par[i]=i,sz[i]=1;
}
int find(int node){
    if(node==par[node]) return node;
    return par[node]=find(par[node]);
}
int min_cardinality(int N) {
    make_set();
    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            move_inside(i);
            move_inside(j);
            int x=press_button();
            if(x==2){
                //same element
                int jj=find(j);
                int ii=find(i);
                if(ii==jj) goto re;
                // dbg(i,j,ii,jj,x);
                if(sz[ii]<sz[jj]) swap(ii,jj);
                par[jj]=ii;
                sz[ii]+=sz[jj];
            }
            re:
                move_outside(i);
                move_outside(j);
        }
    }
    // dbg(press_button());
    set<int> roots;
    for(int i=0;i<N;i++) roots.insert(find(i));
    ll ans=INF;
    // for(auto x:roots) dbg(x,sz[x]);
    for(auto x:roots) ans=min(ans,(ll)sz[x]);
    return (int)ans;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 976 KB Output is correct
2 Correct 1 ms 976 KB Output is correct
3 Correct 1 ms 976 KB Output is correct
4 Correct 1 ms 976 KB Output is correct
5 Correct 1 ms 976 KB Output is correct
6 Correct 140 ms 976 KB Output is correct
7 Correct 188 ms 1064 KB Output is correct
8 Correct 108 ms 976 KB Output is correct
9 Correct 145 ms 976 KB Output is correct
10 Correct 160 ms 976 KB Output is correct
11 Correct 103 ms 1068 KB Output is correct
12 Correct 141 ms 976 KB Output is correct
13 Correct 121 ms 976 KB Output is correct
14 Correct 162 ms 976 KB Output is correct
15 Correct 89 ms 976 KB Output is correct
16 Correct 124 ms 976 KB Output is correct
17 Correct 121 ms 976 KB Output is correct
18 Correct 163 ms 976 KB Output is correct
19 Correct 78 ms 976 KB Output is correct
20 Correct 132 ms 1072 KB Output is correct
21 Correct 148 ms 1068 KB Output is correct
22 Correct 141 ms 1072 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 976 KB Output is correct
2 Correct 1 ms 976 KB Output is correct
3 Correct 1 ms 976 KB Output is correct
4 Correct 1 ms 976 KB Output is correct
5 Correct 1 ms 976 KB Output is correct
6 Correct 140 ms 976 KB Output is correct
7 Correct 188 ms 1064 KB Output is correct
8 Correct 108 ms 976 KB Output is correct
9 Correct 145 ms 976 KB Output is correct
10 Correct 160 ms 976 KB Output is correct
11 Correct 103 ms 1068 KB Output is correct
12 Correct 141 ms 976 KB Output is correct
13 Correct 121 ms 976 KB Output is correct
14 Correct 162 ms 976 KB Output is correct
15 Correct 89 ms 976 KB Output is correct
16 Correct 124 ms 976 KB Output is correct
17 Correct 121 ms 976 KB Output is correct
18 Correct 163 ms 976 KB Output is correct
19 Correct 78 ms 976 KB Output is correct
20 Correct 132 ms 1072 KB Output is correct
21 Correct 148 ms 1068 KB Output is correct
22 Correct 141 ms 1072 KB Output is correct
23 Incorrect 121 ms 976 KB Too many queries.
24 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 976 KB Output is correct
2 Correct 1 ms 976 KB Output is correct
3 Correct 1 ms 976 KB Output is correct
4 Correct 1 ms 976 KB Output is correct
5 Partially correct 1 ms 976 KB Output is partially correct
6 Partially correct 1 ms 976 KB Output is partially correct
7 Incorrect 106 ms 976 KB Too many queries.
8 Halted 0 ms 0 KB -