This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "nile.h"
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
vector<int> parent;
vector<int> sz;
vector<int> mn;
int sm=0;
int getParent(int x){
if(parent[x]==x) return x;
return parent[x]=getParent(parent[x]);
}
void unite(int a, int b){
a=getParent(a); b=getParent(b);
if(a==b) return;
parent[b]=a;
if(sz[a]<sz[b]) swap(a,b);
if(sz[a]%2) sm-=mn[a];
if(sz[b]%2) sm-=mn[b];
sz[a]+=sz[b];
mn[a]=min(mn[a],mn[b]);
if(sz[a]%2) sm+=mn[a];
}
std::vector<int> calculate_costs(std::vector<signed> W, std::vector<signed> A, std::vector<signed> B, std::vector<signed> E) {
int q = sz(E);
int n=sz(W);
mn.resize(n); sz.resize(n); parent.resize(n);
vector<pair<int,int>> e(q);
vector<pair<int,pair<int,int>>> a(n);
for (int i = 0; i < q; i++) e[i]={E[i],i};
for (int i = 0; i < n; i++) a[i]={W[i],{A[i],B[i]}};
sort(all(a));
sort(all(e));
vector<pair<int,int>> df(n-1);
for (int i = 0; i < n-1; i++) df[i]={a[i+1].first-a[i].first,i};
sm=0;
for (int i = 0; i < n; i++)
{
sm+=a[i].second.first;
sz[i]=1;
parent[i]=i;
mn[i]=a[i].second.first-a[i].second.second;
}
sort(all(df));
std::vector<int> R(q, 0);
int j=0;
for (int i = 0; i < q; i++)
{
while(j<n-1){
if(df[j].first>e[i].first) break;
unite(df[j].second,df[i].second+1);
j++;
}
R[e[i].second]=sm;
}
return R;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |