#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <fstream>
#include <iterator>
#include <set>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cctype>
#include <string>
#include <cassert>
#include <set>
#include <bitset>
#include <unordered_set>
#include <numeric>
#define all(a) a.begin(), a.end()
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define ppi pair<int,pair<int,int>>
#define int long long
#define ll long long
using namespace std;
// /\_/\
// (= ._.)
// / > \>
// encouraging cat
const int INF = 10000000000000000;
const int mod = 1000000007;
//const int mod = 998244353;
const int MAXN = 200005;
//ifstream fin('xor.in');
//ofstream fout('xor.out');
ll curr_res = 0;
struct Index {
ll a,b,w;
};
struct Node {
ll parent, min_value, min_index, size, sb;
};
vector<Index> vals;
vector<Node> info;
vector<pair<int,int>> e;
bool cmp(const Index &x, const Index &y) { return x.w < y.w; }
int find_parent(int x)
{
if (x == info[x].parent)
{
return x;
}
return info[x].parent == find_parent(info[x].parent);
}
void remove(Node x)
{
if (x.size % 2 == 0)
{
curr_res -= x.sb;
}
else
{
curr_res -= x.sb - vals[x.min_index].b + vals[x.min_index].a;
}
}
void add(Node x)
{
if (x.size % 2 == 0)
{
curr_res += x.sb;
}
else
{
curr_res += x.sb - vals[x.min_index].b + vals[x.min_index].a;
}
}
pair<Node, Node> merge(Node x,Node y, int ix, int iy)
{
y.parent = ix;
x.size += y.size;
if (y.min_value < x.min_value)
{
x.min_value = y.min_value;
x.min_index = y.min_index;
}
x.sb += y.sb;
return {x,y};
}
void onion (int x, int y)
{
x = find_parent(x);
y = find_parent(y);
if (x == y)
return ;
remove(info[x]);
remove(info[y]);
if (info[y].size > info[x].size)
{
swap(x,y);
}
pair<Node, Node> m = merge(info[x], info[y], x, y);
info[x] = m.first;
info[y] = m.second;
add(info[x]);
}
#undef int long long
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E)
{
int n = A.size();
info.resize(n);
vals.resize(n);
for (int i = 0;i < n;i++)
{
vals[i].a = A[i];
vals[i].b = B[i];
vals[i].w = W[i];
}
sort(all(vals), cmp);
for (int i = 0;i < n;i++)
{
info[i].parent = i;
info[i].min_index = i;
info[i].min_value = vals[i].a - vals[i].b;
info[i].sb = vals[i].b;
info[i].size = 1;
curr_res += vals[i].a;
}
int q = E.size();
e.resize(q);
for (int i = 0;i < q;i++)
{
e[i].first = E[i];
e[i].second = i;
}
sort(all(e));
vector<pair<ll,ll>> diff; //
for (int i = 0;i < n - 1;i++)
{
diff.push_back({vals[i + 1].w - vals[i].w, i});
}
sort(all(diff));
vector<ll> res(q);
int e_index = 0;
for (int i = 0;i < diff.size();i++)
{
if (diff[i].first <= e[e_index].first)
{
int a = diff[i].second;
int b = diff[i].second + 1;
onion(a,b);
}
else
{
res[e[e_index].second] = curr_res;
e_index++;
i--;
}
}
for (; e_index < q;e_index++)
{
res[e[e_index].second] = curr_res;
}
return res;
}
Compilation message
nile.cpp:33:1: warning: multi-line comment [-Wcomment]
33 | // /\_/\
| ^
nile.cpp:114:12: warning: extra tokens at end of #undef directive
114 | #undef int long long
| ^~~~
nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:152:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | for (int i = 0;i < diff.size();i++)
| ~~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
34 ms |
14628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
33 ms |
13376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
33 ms |
13376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
