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 "closing.h"
#include <vector>
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
const int nmax = 2e5 + 5;
ll dx[nmax], dy[nmax];
int p[nmax];
vector<pii> g[nmax];
void filld(int node, int f, ll *d) {
p[node] = f;
for(auto [x, c] : g[node]) {
if(x == f) continue;
d[x] = d[node] + c;
filld(x, node, d);
}
return;
}
int separate(int N, ll S) {
vector<pii> s;
for(int i = 0; i < N; i++) {
s.emplace_back(i, 1);
s.emplace_back(i, 2);
}
sort(all(s), [&](auto a, auto b) {
return (a.second == 1? dx[a.first] : dy[a.first]) < (b.second == 1? dx[b.first] : dy[b.first]);
});
vector<int> occ(N, 0);
int cnt = 0;
for(auto [x, t] : s) {
if(occ[x]) continue;
auto C = (t == 1? dx[x] : dy[x]);
if(S < C) break;
S -= C;
occ[x] = 1;
cnt++;
}
return cnt;
}
signed max_score(signed N, signed X, signed Y, long long S, std::vector<signed> U, std::vector<signed> V, std::vector<signed> W) {
for(int i = 0; i <= N; i++) g[i].clear();
for(int i = 0; i < sz(U); i++) {
g[U[i]].emplace_back(V[i], W[i]);
g[V[i]].emplace_back(U[i], W[i]);
}
dx[X] = dy[Y] = 0;
filld(X, X, dx);
filld(Y, Y, dy);
const int opt1 = separate(N, S);
//cerr << opt1 << '\n';
vector<int> onchain(N, 0);
int t = X;
while(t != Y) {
onchain[t] = 1;
t = p[t];
}
onchain[Y] = 1;
vector<pair<ll, ll>> s;
for(int node = 0; node < N; node++) {
//cerr << onchain[node] << ' ';
if(onchain[node]) {
int a = dx[node], b = dy[node];
if(a > b) swap(a, b);
S -= a;
s.emplace_back(b - a, -1);
}
else {
int a = dx[node], b = dy[node];
if(a > b) swap(a, b);
b -= a;
if(a <= b) {
s.emplace_back(a, -1);
s.emplace_back(b, -1);
}
else {
s.emplace_back(a, b);
}
}
}
//cerr << '\n' << S << '\n';
if(S < 0) return opt1;
int opt2 = 0;
sort(all(s), [&](auto a, auto b) {
auto C = (a.second == -1? 2 * a.first : a.first + a.second);
auto D = (b.second == -1? 2 * b.first : b.first + b.second);
return C < D;
});
for(int it = 0; it < sz(s); it++) {
auto [a, b] = s[it];
if(b == -1) {
if(a > S) break;
S -= a;
opt2++;
}
else {
if(a + b > S) {
for(int j = it + 1; j < sz(s); j++)
a = min(a, s[j].first);
if(S < a) break;
opt2++;
break;
}
else {
S -= a + b;
opt2++;
}
}
}
return max(opt1, opt2);
}
#undef int
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |