이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
struct dsu{
vector<ll> p;
dsu(ll n):p(n,-1){}
ll g(ll i){
return p[i]<0?i:p[i] = g(p[i]);
}
bool m(ll a, ll b){
a = g(a),b = g(b);
if (a==b) return false;
if(p[a]>p[b]) swap(a,b);
p[a] += p[b];
p[b] = a;
return true;
}
};
int min_cardinality(int n) {
mt19937_64 mt(random_device{}());
vector<ll> a(n);
iota(a.begin(),a.end(),0);
dsu d(n);
ll run = 1;
while(run){
run = 0;
shuffle(a.begin(),a.end(),mt);
vector<ll> v;
for(ll i : a) if(d.p[i]<0) v.push_back(i);
ll l = 0;
for(ll i = 0;i<v.size();i++){
move_inside(v[i]);
if (i>0&&press_button()>1){
do{
move_outside(v[l++]);
}while(press_button()>1);
d.m(v[l-1],v[i]);
run = 1;
}
}
while(l<v.size())move_outside(v[l++]);
}
ll ans = -n;
for(ll i : d.p) if(i<0)ans = max(ans,i);
return -ans;
}
컴파일 시 표준 에러 (stderr) 메시지
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:32:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(ll i = 0;i<v.size();i++){
| ~^~~~~~~~~
insects.cpp:42:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | while(l<v.size())move_outside(v[l++]);
| ~^~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |