#include "closing.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll big = 2e18;
struct line{
ll i,w;
};
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W){
ll n = N;
ll x = X;
ll y = Y;
ll k = K;
vector<vector<line>> con(n);
ll is_line = 1
for(ll i = 0;i<n-1;i++){
con[U[i]].push_back({V[i],W[i]});
con[V[i]].push_back({U[i],W[i]});
if(U[i]!=i||V[i]!=i+1) is_line = 0;
}
if (is_line){
vector<ll> w = W;
vector<ll> pw(n,0);
for(ll i = 1;i<n;i++) pw[i+1] = pw[i]+w[i];
vector<ll> v,cc(n,0);
for(ll i = 0;i<x;i++){
v.push_back(cc[i] = pw[x]-pw[i]);
}
for(ll i = y+1;i<n;i++){
v.push_back(cc[i] = pw[i]-pw[y]);
}
vector<ll> pc(n+1,0);
for(ll i = 0;i<n;i++) pc[i+1] = cc[i]+pc[i];
sort(v.begin(),v.end());
for(ll i = 1;i<v.size();i++) v[i]+=v[i-1];
ll ans = 0;
vector<ll> h(n,0),h1(n,0);
ll lv1 = 0;
for(ll i = x;i<n;i++){
h[i] = pw[i]-pw[x];
h1 = h;
lv1 += h[i];
ll lv2 = lv1;
for(ll j = y;j>=0;j--){
h1[j] = max(h[j],pw[y]-pw[j]);
lv2 += max(pw[y]-pw[j]-h[j],0ll);
if (lv2>k) break;
ll g = 2+i-x+y-j;
vector<ll> v;
for(ll p = 0;p<x;p++){
v.push_back(max(0ll,pw[x]-pw[p]-h[p]));
}
for(ll p = y+1;p<n;p++){
v.push_back(max(0ll,pw[p]-pw[y]-h[p]));
}
sort(v.begin(),v.end());
ll cur = lv2;
for(ll i : v) if(cur+i<=k){
cur += i;
g++;
}
ans = max(ans,g);
}
}
return ans;
}
vector<ll> dis1(n,big),dis2(n,big);
{
function<void(ll,ll)> dfs;
dfs = [&](ll i, ll v){
if(dis1[i]>v){
dis1[i] = v;
for(auto [j,w] : con[i]){
dfs(j,v+w);
}
}
};
dfs(x,0);
}
{
function<void(ll,ll)> dfs;
dfs = [&](ll i, ll v){
if(dis2[i]>v){
dis2[i] = v;
for(auto [j,w] : con[i]){
dfs(j,v+w);
}
}
};
dfs(y,0);
}
ll l = 0, r = big;
while(l<r){
ll m = l+r+1>>1;
ll sm = 0;
for(ll i = 0;i<n;i++){
ll mi = min(dis1[i],dis2[i]);
ll mx = max(dis1[i],dis2[i]);
if(m>=mx) sm+=mx;
else if(m>=mi) sm+=mi;
}
if(sm>k) r = m-1;
else l = m;
}
ll cur = 0, ans = 0;
vector<ll> v;
for(ll i = 0;i<n;i++){
ll mi = min(dis1[i],dis2[i]);
ll mx = max(dis1[i],dis2[i]);
if (mx<=l){
cur += mx;
ans += 2;
}else if (mi<=l){
cur += mi;
ans += 1;
if (mx==l+1){
v.push_back(mx-mi);
}
}else if(mi==l+1){
v.push_back(mi);
}
}
sort(v.begin(),v.end());
for(ll i : v){
if(cur+i<=k){
ans += 1;
cur += i;
}
}
return ans;
}
Compilation message
closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:19:5: error: expected ',' or ';' before 'for'
19 | for(ll i = 0;i<n-1;i++){
| ^~~
closing.cpp:19:18: error: 'i' was not declared in this scope
19 | for(ll i = 0;i<n-1;i++){
| ^
closing.cpp:25:24: error: conversion from 'vector<int>' to non-scalar type 'vector<long long int>' requested
25 | vector<ll> w = W;
| ^
closing.cpp:38:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(ll i = 1;i<v.size();i++) v[i]+=v[i-1];
| ~^~~~~~~~~
closing.cpp:97:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
97 | ll m = l+r+1>>1;
| ~~~^~
