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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()
const int N = 500 + 3;
const int M = 1e5 + 3;
const int Q = 1e6 + 3;
const int INF = 1e9;
int n, m, q;
array<ll, 3> e[M];
ll x[Q];
struct DSU{
int sz[N], par[N];
void init(int n){
for(int i = 1; i <= n; ++i)
sz[i] = 1, par[i] = i;
}
int getP(int x){
if(par[x] == x) return x;
return par[x] = getP(par[x]);
}
bool unite(int a, int b){
a = getP(a), b = getP(b);
if(a == b) return false;
if(sz[a] < sz[b]) swap(a, b);
sz[a] += sz[b];
par[b] = a;
return true;
}
} dsu;
vector<int> pr[M], su[M];
pair<ll, int> get_ans(const vector<int> &e1, const vector<int> &e2, ll x, int ptr){
ll ans = 0;
int cnt = 0;
vector<pair<int, int>> e3;
int ptr1 = 0, ptr2 = 0;
while(ptr1 != e1.size() && ptr2 != e2.size()){
int cost1 = x - e[e1[ptr1]][0];
int cost2 = e[e2[ptr2]][0] - x;
if(cost1 < cost2)
e3.push_back({cost1, e1[ptr1++]});
else
e3.push_back({cost2, e2[ptr2++]});
}
while(ptr1 != e1.size()){
int cost1 = x - e[e1[ptr1]][0];
e3.push_back({cost1, e1[ptr1++]});
}
while(ptr2 != e2.size()){
int cost2 = e[e2[ptr2]][0] - x;
e3.push_back({cost2, e2[ptr2++]});
}
dsu.init(n);
for(auto [cost, idx]: e3){
if(dsu.unite(e[idx][1], e[idx][2])){
ans += cost;
if(idx >= ptr)
++cnt;
}
}
return {ans, cnt};
}
ll bin_search_next_change(const vector<int> &e1, const vector<int> &e2, ll x, int ptr, int cnt){
ll l = x + 1, r = INF + 1;
while(l != r){
ll mid = (l + r) >> 1;
if(get_ans(e1, e2, mid, ptr).second > cnt)
r = mid;
else
l = mid + 1;
}
return l;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i = 0; i < m; ++i){
cin >> e[i][1] >> e[i][2] >> e[i][0];
}
sort(e, e + m);
pr[0] = {0};
for(int i = 1; i < m; ++i){
dsu.init(n);
pr[i].push_back(i);
for(int idx: pr[i - 1])
if(dsu.unite(e[idx][1], e[idx][2]))
pr[i].push_back(idx);
}
su[m - 1] = {m - 1};
for(int i = m - 2; i >= 0; --i){
dsu.init(n);
su[i].push_back(i);
for(int idx: su[i + 1])
if(dsu.unite(e[idx][1], e[idx][2]))
su[i].push_back(idx);
}
ll ans = 0, cnt = 0, prevx = -INF, next_change;
auto p = get_ans({}, su[0], prevx, 0);
ans = p.first;
cnt = p.second;
next_change = bin_search_next_change({}, su[0], prevx, 0, cnt);
int ptr = 0;
cin >> q;
for(int i = 0; i < q; ++i){
cin >> x[i];
while(ptr != m && x[i] >= e[ptr][0]){
++ptr;
vector<int> e1;
if(0 <= ptr - 1){
e1 = pr[ptr - 1];
}
vector<int> e2;
if(ptr <= m - 1){
e2 = su[ptr];
}
auto p = get_ans(e1, e2, x[i], ptr);
ans = p.first;
cnt = p.second;
prevx = x[i];
next_change = bin_search_next_change(e1, e2, prevx, ptr, cnt);
}
if(x[i] < next_change){
cout << ans + (ll)(n - 1 - 2 * cnt) * (x[i] - prevx) << "\n";
}
else{
vector<int> e1;
if(0 <= ptr - 1){
e1 = pr[ptr - 1];
}
vector<int> e2;
if(ptr <= m - 1){
e2 = su[ptr];
}
auto p = get_ans(e1, e2, x[i], ptr);
ans = p.first;
cnt = p.second;
prevx = x[i];
next_change = bin_search_next_change(e1, e2, prevx, ptr, cnt);
cout << ans << "\n";
}
}
}
Compilation message (stderr)
reconstruction.cpp: In function 'std::pair<long long int, int> get_ans(const std::vector<int>&, const std::vector<int>&, ll, int)':
reconstruction.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | while(ptr1 != e1.size() && ptr2 != e2.size()){
| ~~~~~^~~~~~~~~~~~
reconstruction.cpp:50:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | while(ptr1 != e1.size() && ptr2 != e2.size()){
| ~~~~~^~~~~~~~~~~~
reconstruction.cpp:59:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | while(ptr1 != e1.size()){
| ~~~~~^~~~~~~~~~~~
reconstruction.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | while(ptr2 != e2.size()){
| ~~~~~^~~~~~~~~~~~
# | 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... |