oj.uz

Submission #1064134

# Submission time Handle Problem Language Result Execution time Memory
1064134 2024-08-18T09:32:17 Z MarwenElarbi Rarest Insects (IOI22_insects) C++17
10 / 100
 215 ms 16936 KB 
#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
#define pb push_back
#define ll long long
#define fi first
#define se second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int nax=5005;
int parent[nax];
int sz[nax];
int find(int x){
  if(parent[x]==x) return x;
  return parent[x]=find(parent[x]);
}
bool sameset(int x,int y){
  return find(x)==find(y);
}
void joinset(int x,int y){
  x=find(x);
  y=find(y);
  parent[x]=y;
  sz[y]+=sz[x];
  return; 
}
int min_cardinality(int N) {
  vector<pair<int,int>> tab;
  for (int i = 0; i < N; ++i)
  {
    parent[i]=i;
    sz[i]=1;
  }
  for (int i = 0; i < N; ++i)
  {
    for (int j = i+1; j < N; ++j)
    {
        tab.pb({i,j});
    }
  }
  int cnt=0;
  shuffle(tab.begin(),tab.end(),rng);
  for (int i = 0; i < min(N*(N-1)/2,20000); ++i)
  {
    if(sameset(tab[i].fi,tab[i].se)) continue;
    cnt++;
    move_inside(tab[i].fi);
    move_inside(tab[i].se);
    int a=press_button();
    move_outside(tab[i].fi);
    move_outside(tab[i].se);
    if(a==2) joinset(tab[i].fi,tab[i].se);
  }
  int mn=1e9;
  for (int i = 0; i < N; ++i)
  {
    mn=min(mn,sz[find(i)]);
  }
  return mn;
}

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 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 2 ms 724 KB Output is correct
7 Correct 133 ms 724 KB Output is correct
8 Correct 128 ms 724 KB Output is correct
9 Correct 121 ms 724 KB Output is correct
10 Correct 2 ms 720 KB Output is correct
11 Correct 98 ms 724 KB Output is correct
12 Correct 91 ms 724 KB Output is correct
13 Correct 126 ms 724 KB Output is correct
14 Correct 91 ms 724 KB Output is correct
15 Correct 106 ms 724 KB Output is correct
16 Correct 133 ms 724 KB Output is correct
17 Correct 104 ms 724 KB Output is correct
18 Correct 108 ms 724 KB Output is correct
19 Correct 115 ms 724 KB Output is correct
20 Correct 135 ms 724 KB Output is correct
21 Correct 123 ms 724 KB Output is correct
22 Correct 109 ms 724 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 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 2 ms 724 KB Output is correct
7 Correct 133 ms 724 KB Output is correct
8 Correct 128 ms 724 KB Output is correct
9 Correct 121 ms 724 KB Output is correct
10 Correct 2 ms 720 KB Output is correct
11 Correct 98 ms 724 KB Output is correct
12 Correct 91 ms 724 KB Output is correct
13 Correct 126 ms 724 KB Output is correct
14 Correct 91 ms 724 KB Output is correct
15 Correct 106 ms 724 KB Output is correct
16 Correct 133 ms 724 KB Output is correct
17 Correct 104 ms 724 KB Output is correct
18 Correct 108 ms 724 KB Output is correct
19 Correct 115 ms 724 KB Output is correct
20 Correct 135 ms 724 KB Output is correct
21 Correct 123 ms 724 KB Output is correct
22 Correct 109 ms 724 KB Output is correct
23 Correct 16 ms 6344 KB Output is correct
24 Correct 147 ms 4552 KB Output is correct
25 Incorrect 166 ms 4552 KB Wrong answer.
26 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 Correct 1 ms 344 KB Output is correct
6 Partially correct 1 ms 344 KB Output is partially correct
7 Correct 85 ms 16936 KB Output is correct
8 Partially correct 215 ms 16832 KB Output is partially correct
9 Incorrect 209 ms 16832 KB Wrong answer.
10 Halted 0 ms 0 KB -