#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
const int maxn = 2e5;
struct edge {
int to, wei;
};
int ans;
int n, x, y, k;
vector<pii > g[1 + maxn];
int d[2][1 + maxn];
bool done[2][1 + maxn];
void dfs(int cur, int idx, int par) {
for(pii nei : g[cur]) {
if(nei.fi != par) {
d[idx][nei.fi] = d[idx][cur] + nei.se;
dfs(nei.fi, idx, cur);
}
}
}
struct item {
int val;
int pos;
int type;
bool operator < (const item & other) const {
return val > other.val;
}
};
int sum, cur_ans;
priority_queue<item> q;
void push_for(item cur) {
for(pii nei : g[cur.pos]) {
if(!done[cur.type][nei.fi]) {
if(!done[cur.type^1][nei.fi]) {
q.push({d[cur.type][nei.fi], nei.fi, cur.type});
} else {
q.push({max(0ll, d[cur.type][nei.fi] - d[cur.type^1][nei.fi]), nei.fi, cur.type});
}
}
}
}
bool topush;
bool eval(item cur) {
if(done[cur.type][cur.pos]) {
return true;
}
if(cur.val > k - sum) {
return false;
}
sum += cur.val;
cur_ans++;
done[cur.type][cur.pos] = true;
if(topush) {
push_for(cur);
}
return true;
}
vector<int> path;
bool path_dfs(int cur, int par) {
if(cur == y) {
path.pb(y);
return true;
}
for(pii nei : g[cur]) {
if(nei.fi != par) {
bool res = path_dfs(nei.fi, cur);
if(res) {
path.pb(cur);
return true;
}
}
}
return false;
}
bool do_this(int i, int type, bool inc) {
if(type == 0) {
int bound = i - 1;
if(inc) {
bound = i;
}
for(int j = 0; j <= bound; j++) {
if(!eval({d[type][path[j]], path[j], type})) {
return false;
}
}
} else { // this might be wrong !!!!!
int bound = i + 1;
if(inc) {
bound = i;
}
for(int j = path.size() - 1; j >= bound; j--) {
if(!eval({d[type][path[j]], path[j], type})) {
return false;
}
}
}
return true;
}
int thing[1 + maxn];
void inc(int idx, int type) {
int newval = max(thing[idx], d[type][idx]);
sum += newval - thing[idx];
thing[idx] = newval;
cur_ans++;
}
void solve() {
dfs(x, 0, -1);
dfs(y, 1, -1);
for(int i = x; i <= n; i++) {
sum = 0, cur_ans = 0;
for(int j = 1; j <= n; j++) {
thing[j] = 0;
}
for(int j = x; j <= min(y - 1, i); j++) {
inc(j, 0);
}
for(int j = y; j <= i; j++) {
inc(j, 1);
inc(j, 0);
}
for(int j = y; j >= 1; j--) {
if(j != y) {
if(j >= x) {
inc(j, 1);
} else {
inc(j, 0);
inc(j, 1);
}
}
if(sum > k) {
break;
}
/*for(int l = y - 1; l >= max(j, x); l--) {
inc(l, 1);
}
for(int l = x - 1; l >= j; l--) {
inc(l, 0);
inc(l, 1);
}*/
vector<int> v;
for(int l = 1; l < min(x, j); l++) {
v.pb(d[0][l]);
}
for(int l = max(i, y) + 1; l <= n; l++) {
v.pb(d[1][l]);
}
sort(v.begin(), v.end());
int extra = 0; int extra_sum = 0;
for(int tmp : v) {
if(tmp + sum + extra_sum <= k) {
extra_sum += tmp;
extra++;
}
}
cur_ans += extra;
ans = max(ans, cur_ans);
cur_ans -= extra;
}
}
q.push({0, x, 0});
q.push({0, y, 1});
topush = true;
sum = 0, cur_ans = 0;
while(!q.empty()) {
item cur = q.top();
q.pop();
bool res = eval(cur);
if(!res) {
break;
}
}
ans = cur_ans;
path_dfs(x, -1);
reverse(path.begin(), path.end());
for(int i = 0; i < path.size(); i++) {
for(int i = 1; i <= n; i++) {
done[0][i] = done[1][i] = false;
}
sum = 0, cur_ans = 0;
while(!q.empty()) {
q.pop();
}
topush = false;
if(d[0][path[i]] < d[1][path[i]]) {
if(!do_this(i, 0, true)) {
continue;
}
if(!do_this(i, 1, false)) {
continue;
}
if(!eval({d[1][path[i]] - d[0][path[i]], path[i], 1})) {
continue;
}
} else {
if(!do_this(i, 1, true)) {
continue;
}
if(!do_this(i, 0, false)) {
continue;
}
if(!eval({d[0][path[i]] - d[1][path[i]], path[i], 0})) {
continue;
}
}
while(!q.empty()) {
q.pop();
}
topush = true;
for(int i = 1; i <= n; i++) {
for(int j = 0; j < 2; j++) {
if(done[j][i]) {
push_for({-1, i, j});
}
}
}
while(!q.empty()) {
item cur = q.top();
q.pop();
bool res = eval(cur);
if(!res) {
break;
}
}
ans = max(ans, cur_ans);
}
}
void reset() {
ans = 0;
for(int i = 1; i <= n; i++) {
g[i].clear();
d[0][i] = d[1][i] = 0;
done[0][i] = done[1][i] = false;
thing[i] = 0;
}
sum = 0, cur_ans = 0;
while(!q.empty()) {
q.pop();
}
path.clear();
//
}
signed max_score(signed N, signed X, signed Y, int K,
vector<signed> U, vector<signed> V, vector<signed> W) {
reset();
n = N, x = X, y = Y, k = K;
x++;
y++;
for(int i = 0; i < n - 1; i++) {
int a = U[i], b = V[i], c = W[i];
a++;
b++;
g[a].pb(mp(b, c));
g[b].pb(mp(a, c));
}
solve();
return ans;
}
Compilation message
closing.cpp: In function 'void solve()':
closing.cpp:198:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
198 | for(int i = 0; i < path.size(); i++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1043 ms |
32476 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4956 KB |
1st lines differ - on the 1st token, expected: '30', found: '27' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4956 KB |
1st lines differ - on the 1st token, expected: '30', found: '27' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4956 KB |
1st lines differ - on the 1st token, expected: '30', found: '27' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4956 KB |
1st lines differ - on the 1st token, expected: '30', found: '27' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4956 KB |
1st lines differ - on the 1st token, expected: '30', found: '27' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4956 KB |
1st lines differ - on the 1st token, expected: '30', found: '27' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4956 KB |
1st lines differ - on the 1st token, expected: '30', found: '27' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4956 KB |
1st lines differ - on the 1st token, expected: '30', found: '27' |
| 4 |
Halted |
0 ms |
0 KB |
- |
