Submission #1074389

#TimeUsernameProblemLanguageResultExecution timeMemory
1074389ZicrusRarest Insects (IOI22_insects)C++17
10 / 100
152 ms592 KiB
#include <bits/stdc++.h> #include "insects.h" using namespace std; typedef long long ll; int n; vector<int> lnk, sz; int find(int a) { if (lnk[a] != a) return lnk[a] = find(lnk[a]); return lnk[a]; } void unite(int a, int b) { a = find(a); b = find(b); if (a == b) return; lnk[a] = b; sz[b] += sz[a]; } int min_cardinality(int N) { n = N; lnk = vector<int>(n); sz = vector<int>(n, 1); for (int i = 0; i < n; i++) lnk[i] = i; for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { if (find(i) == find(j)) continue; move_inside(i); move_inside(j); if (press_button() > 1) unite(i, j); move_outside(i); move_outside(j); } } int mn = n; for (int i = 0; i < n; i++) { if (i != lnk[i]) continue; mn = min(mn, sz[i]); } return mn; } #ifdef TEST #include "grader.cpp" #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...