| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1103501 | ezzzay | 나일강 (IOI24_nile) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define ll long long
const int N=3e5+5;
int par[N];
int sbtr[N];
int H;
int mn[N],mx[N];
int find(int x){
if(par[x]==x)return x;
return par[x]=find(par[x]);
}
void unite(int x, int y){
int px=find(x),py=find(y);
if(px==py)return;
if(sbtr[py]>sbtr[px])swap(px,py);
if(sbtr[py]%2 and sbtr[px]%2){
H-=mx[py];
H-=mx[px];
}
else if(sbtr[py]%2){
H+=mn[py];
H-=max(mx[py],mx[px]);
}
else if(sbtr[px]%2){
H+=mn[px];
H-=max(mx[py],mx[px]);
}
mx[py]=max(mx[py],mx[px]);
mn[py]=min(mn[py],mn[px]);
sbtr[px]+=sbtr[py];
par[py]=px;
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
H=0;
for(auto p:A)H+=p;
int q = (int)E.size();
int n = W.size();
for(int i=0;i<n;i++){
par[i]=i;
sbtr[i]=1;
mn[i]=A[i]-B[i];
mx[i]=A[i]-B[i];
}
vector<ll>ans(q);
vector<pair<ll,ll> >v;
vector<pair<ll, pair<int,int> > >vc;
for(int i=0;i<n;i++){
v.pb({W[i],i});
}
sort(v.begin(),v.end());
for(int i=1;i<n;i++){
int x=abs(v[i].ff-v[i-1].ff);
int a=v[i-1].ss,b=v[i].ss;
vc.pb({x,{a,b}});
}
sort(vc.begin(),vc.end());
int idx=0;
vector<pair<int,int>>vec;
for(int i=0;i<q;i++){
vec.pb({E[i],i});
}
sort(vec.begin(),vec.end());
for(int f=0;f<q;f++){
ll d=vec[f].ff;
int k=vec[f].ss;
while(vc[idx].ff<=d and idx<vc.size()){
int a=vc[idx].ss.ff,b=vc[idx].ss.ss;
unite(a,b);
idx++;
}
ans[k]=H;
}
return ans;
}
int main() {
int N=5;
std::vector<int> W={15, 12, 2, 10, 21}, A={5, 4, 5, 6, 3}, B={1, 2, 2, 3, 2};
int Q=3;
std::vector<int> E={5,9,1};
std::vector<long long> R = calculate_costs(W, A, B, E);
int S = (int)R.size();
for (int j = 0; j < S; j++)
printf("%lld\n", R[j]);
fclose(stdout);
return 0;
}