#include <bits/stdc++.h>
#include "closing.h"
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
vector<vector<ii> >adj;
priority_queue<ii,vector<ii>,greater<ii> >pq;
int max_score(int n, int x, int y, long long k,vector<int>u, vector<int> v, vector<int> w){
adj.assign(n+5,vector<ii>());
f(i,0,n-1){
adj[u[i]].pb(ii(v[i],w[i]));
adj[v[i]].pb(ii(u[i],w[i]));
}
ll dist[n][3];
f(i,0,n){
dist[i][0] = dist[i][1] = 1e18;
}
dist[x][0] = 0;
pq.push(ii(0,x));
while(!pq.empty()){
ii f = pq.top();
pq.pop();
ll w = f.F,u = f.S;
if(dist[u][0] < w){
continue;
}
for(auto x:adj[u]){
if(x.S + dist[u][0] < dist[x.F][0]){
dist[x.F][0] = x.S + dist[u][0];
pq.push(ii(dist[x.F][0],x.F));
}
}
}
dist[y][1] = 0;
pq.push(ii(0,y));
while(!pq.empty()){
ii f = pq.top();
pq.pop();
ll w = f.F,u = f.S;
if(dist[u][1] < w){
continue;
}
for(auto x:adj[u]){
if(x.S + dist[u][1] < dist[x.F][1]){
dist[x.F][1] = x.S + dist[u][1];
pq.push(ii(dist[x.F][1],x.F));
}
}
}
ll sum = 0;
f(i,0,n){
dist[i][2] = max(dist[i][0],dist[i][1]);
}
vector<ll>other,q;
f(i,0,x){
other.pb(dist[i][0]);
}
f(i,y+1,n){
other.pb(dist[i][1]);
}
sort(all(other));
q.pb(0);
for(auto x:other){
q.pb(q.back() + x);
}
f(i,x,y+1){
sum += dist[i][1];
}
int ans = 0;
f(i,x,y+1){
ll cur = sum;
f(j,i,y+1){
cur -= dist[i][1];
cur += dist[i][2];
ll num = k - cur;
if(num >= 0){
int siz = y - x + 1;
siz += j - i + 1;
int pos = upper_bound(all(q),num) - q.begin() - 1;
siz += pos;
ans = max(ans,siz);
}
}
sum -= dist[i][1];
sum += dist[i][0];
}
sum = 0;
f(i,x,y+1){
sum += dist[i][2];
}
int siz = 2 * (y - x + 1);
ll num = k - sum;
if(num >= 0){
ans = max(ans,siz);
ll d = dist[y][0];
f(i,0,(ll)(other.size())){
num -= other[i];
if(num >= 0){
ans = max(ans,siz + (int)(i+1) + min((int)(i+1),(int)(num / d)));
}
}
}
int res = 0;
vector<ll>kame;
f(i,0,n){
kame.pb(min(dist[i][0],dist[i][1]));
}
sort(all(kame));
f(i,0,n){
if(kame[i] <= k){
k -= kame[i];
res++;
}
}
ans = max(ans,res);
return ans;
}
/*
int main()
{
int Q;
assert(1 == scanf("%d", &Q));
std::vector<int> N(Q), X(Q), Y(Q);
std::vector<long long> K(Q);
std::vector<std::vector<int>> U(Q), V(Q), W(Q);
for (int q = 0; q < Q; q++)
{
assert(4 == scanf("%d %d %d %lld", &N[q], &X[q], &Y[q], &K[q]));
U[q].resize(N[q] - 1);
V[q].resize(N[q] - 1);
W[q].resize(N[q] - 1);
for (int i = 0; i < N[q] - 1; ++i)
{
assert(3 == scanf("%d %d %d", &U[q][i], &V[q][i], &W[q][i]));
}
}
fclose(stdin);
std::vector<int> result(Q);
for (int q = 0; q < Q; q++)
{
result[q] = max_score(N[q], X[q], Y[q], K[q], U[q], V[q], W[q]);
}
for (int q = 0; q < Q; q++)
{
printf("%d\n", result[q]);
}
fclose(stdout);
return 0;
}
*/
/*
2
7 0 2 10
0 1 2
0 3 3
1 2 4
2 4 2
2 5 5
5 6 3
4 0 3 20
0 1 18
1 2 1
2 3 19
1
4 0 3 20
0 1 18
1 2 1
2 3 19
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
256 ms |
30536 KB |
Output is correct |
| 2 |
Execution timed out |
1039 ms |
29128 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
