#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long // remove when necessary
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define ll long long
const int MAX = 1e18;
const int mxN = 2e5 + 1;
int dist[mxN][2];
int cost[mxN][3][3];
vector<pii> adj[mxN];
int n, k;
vector<int> dest;
int pos[mxN];
multiset<pii> ms[3][3];
void reset() {
for (int i = 1; i <= n; i++) {
adj[i].clear();
}
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
ms[i][j].clear();
}
}
}
void change(int from, int to) {
k -= (*ms[from][to].begin()).ff;
int ptr = (*ms[from][to].begin()).ss;
pos[ptr] = to;
for (int i = 0; i < 3; i++) {
if (i == from) continue;
ms[from][i].erase(ms[from][i].find({cost[ptr][from][i], ptr}));
}
for (int i = 0; i < 3; i++) {
if (i == to) continue;
ms[to][i].insert({cost[ptr][to][i], ptr});
}
}
int calc(vector<pii> &v) {
int res = 0;
for (pii &cur : v) {
if (ms[cur.ff][cur.ss].empty()) return MAX;
res += (*ms[cur.ff][cur.ss].begin()).ff;
}
return res;
};
void FindCost() {
priority_queue<pii, vector<pii>, greater<pii>> pq;
for (int i = 0; i < 2; i++) {
for (int j = 1; j <= n; j++) {
dist[j][i] = (j == dest[i] ? 0 : MAX);
}
pq.push({0, dest[i]});
while (!pq.empty()) {
pii cur = pq.top();
pq.pop();
if (cur.ff > dist[cur.ss][i]) continue;
for (pii &v : adj[cur.ss]) {
if (cur.ff + v.ss < dist[v.ff][i]) {
dist[v.ff][i] = cur.ff + v.ss;
pq.push({dist[v.ff][i], v.ff});
}
}
}
}
for (int i = 1; i <= n; i++) {
cost[i][0][0] = 0;
cost[i][0][1] = min(dist[i][0], dist[i][1]);
cost[i][0][2] = max(dist[i][0], dist[i][1]);
cost[i][1][0] = -cost[i][0][1];
cost[i][1][1] = 0;
cost[i][1][2] = cost[i][0][2] - cost[i][0][1];
cost[i][2][0] = -cost[i][0][2];
cost[i][2][1] = -cost[i][1][2];
cost[i][2][2] = 0;
}
}
int32_t max_score(int32_t N, int32_t X, int32_t Y, long long K,
vector<int32_t> U, vector<int32_t> V, vector<int32_t> W)
{
n = N; k = K; dest = {++X, ++Y};
if (dest[0] > dest[1]) swap(dest[0], dest[1]);
reset();
for (int i = 0; i < N - 1; i++) {
U[i]++; V[i]++;
adj[U[i]].pb({V[i], W[i]});
adj[V[i]].pb({U[i], W[i]});
}
FindCost();
for (int i = 1; i <= n; i++) {
// cout << cost[i][0][1] << ' ' << cost[i][0][2] << endl;
}
int finans = 0;
for (int xr = dest[0]; xr <= n; xr++) {
for (int yl = dest[1]; yl >= 1; yl--) {
int curcost = 0;
for (int i = 1; i <= n; i++) {
curcost += cost[i][0][(dest[0] <= i && i <= xr) + (yl <= i && i <= dest[1])];
}
// cerr << dest[0] << ' ' << dest[1] << ' ' << xr << ' ' << yl << ' ' << curcost << endl;
if (curcost > k) continue;
int ptr = dest[1];
while (ptr < n) {
int ncost = curcost;
if (ptr + 1 <= xr) ncost += cost[ptr + 1][1][2];
else ncost += cost[ptr + 1][0][1];
if (ncost <= k) {
curcost = ncost;
ptr++;
} else break;
}
// cerr << xr << ' ' << yl << ' ' << ptr << ' ' << curcost << endl;
finans = max(finans, (xr - dest[0] + 1) + (ptr - yl + 1));
for (int xl = dest[0] - 1; xl >= 1; xl--) {
if (yl <= xl) curcost += cost[xl][1][2];
else curcost += cost[xl][0][1];
while (ptr > dest[1] && curcost > k) {
if (ptr <= xr) curcost -= cost[ptr][1][2];
else curcost -= cost[ptr][0][1];
}
if (curcost <= k) {
// cerr << xl << ' ' << xr << ' ' << yl << ' ' << ptr << " | ";
// cerr << finans << ' ' << curcost << endl;
finans = max(finans, (xr - xl + 1) + (ptr - yl + 1));
}
}
}
}
return finans;
for (int i = 1; i <= n; i++) {
pos[i] = 0;
ms[0][1].insert({cost[i][0][1], i});
ms[0][2].insert({cost[i][0][2], i});
}
vector<vector<pii>> consider[2];
// operation with +1:
consider[1].pb({{0, 1}});
consider[1].pb({{1, 2}});
consider[1].pb({{0, 2}, {2, 1}});
consider[1].pb({{0, 2}, {1, 0}});
// operation with +0:
consider[0].pb({{0, 1}, {1, 0}});
consider[0].pb({{1, 2}, {2, 1}});
consider[0].pb({{0, 2}, {2, 0}});
consider[0].pb({{0, 1}, {2, 1}});
consider[0].pb({{1, 2}, {1, 0}});
consider[0].pb({{0, 1}, {1, 2}, {2, 0}});
consider[0].pb({{0, 2}, {2, 1}, {1, 0}});
while (true) {
bool done = false;
for (vector<pii> &v : consider[1]) {
int res = calc(v);
if (res <= k) {
for (pii &cur : v) change(cur.ff, cur.ss);
done = true;
break;
}
}
if (done) continue;
for (vector<pii> &v : consider[0]) {
int res = calc(v);
if (res < 0) {
for (pii &cur : v) change(cur.ff, cur.ss);
done = true;
break;
}
}
if (done) continue;
break;
}
int ans = 0;
// for (int i = 1; i <= n; i++) cerr << pos[i] << ' ';
// cerr << endl;
for (int i = 1; i <= n; i++) ans += pos[i];
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1063 ms |
37216 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4948 KB |
1st lines differ - on the 1st token, expected: '30', found: '35' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4948 KB |
1st lines differ - on the 1st token, expected: '30', found: '35' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4948 KB |
1st lines differ - on the 1st token, expected: '30', found: '35' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4948 KB |
1st lines differ - on the 1st token, expected: '30', found: '35' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4948 KB |
1st lines differ - on the 1st token, expected: '30', found: '35' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4948 KB |
1st lines differ - on the 1st token, expected: '30', found: '35' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4948 KB |
1st lines differ - on the 1st token, expected: '30', found: '35' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4948 KB |
1st lines differ - on the 1st token, expected: '30', found: '35' |
| 4 |
Halted |
0 ms |
0 KB |
- |
