// hola soy Dember :D
// 31/03/2024
#include "closing.h"
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define f first
#define s second
#define Z size()
#define pb push_back
#define bp pop_back
#define fo(x,y,z) for(ll x=y; x<=z; x++)
#define of(x,y,z) for(ll x=y; x>=z; x--)
#define all(n) n.begin(), n.end()
#define arr(x,y,z) x+y, x+y+z
using namespace std;
ll n, x, y, k;
ll ans;
vector<vector<pll>> a(n);
vector<map<ll,ll>> vis(n+1), dis(n+1);
void q1(){
queue<int> q;
q.push(x);
while(!q.empty()){
auto u = q.front(); q.pop();
for(auto &e:a[u]){
ll v=e.f, w=e.s;
if(dis[x].count(v))continue;
dis[x][v]=dis[x][u]+w;
q.push(v);
}
}
return;
}
int max_score(int N, int X, int Y, ll K, vector<int>U, vector<int>V, vector<int>W) {
n=N;x=X;y=Y;k=K;
a.resize(n); dis.resize(n+1); vis.resize(n+1);
fo(i,0,n-2)a[U[i]].pb({V[i],W[i]}), a[V[i]].pb({U[i],W[i]});
dis[x][x]=dis[y][y]=0;
swap(x,y);
q1();
swap(x,y);
q1();set<pair<int,pll>> q;
vector<ll> c(n);
vector<map<ll,pair<ll,pll>>> l(n);
vector<map<ll,ll>> in(n);
q.insert({0,{x,x}});
q.insert({0,{y,y}});
l[x][x]={0,{x,x}};
l[y][y]={0,{y,y}};
in[x][x]=1;
in[y][y]=1;
while(!q.empty()) {
auto it=*q.begin(); q.erase(q.begin());
if (it.f>k) return ans;
ll xd=it.f, u=it.s.f, z=it.s.s, dm;
ans++;
k-=xd;
dm=dis[z][u];
c[u]=max(c[u], dm);
vis[z][u]=1;
in[z][u]=0;
if(in[x][u]){
dm=dis[x][u]-c[u];
q.erase(l[x][u]);
l[x][u]={max(dm,0ll),{u,x}};
q.insert(l[x][u]);
}
if(in[y][u]){
dm=dis[y][u]-c[u];
q.erase(l[y][u]);
l[y][u]={max(dm,0ll),{u,y}};
q.insert(l[y][u]);
}
for(auto &e:a[u]){
ll ola=e.f;
if (vis[z][ola]) continue;
ll ace=dis[z][ola];
ace=max(ace-c[ola],0ll);
q.insert({ace,{ola,z}});
in[z][ola]=1;
l[z][ola]={ace,{ola,z}};
}
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
382 ms |
84492 KB |
Output is correct |
2 |
Correct |
391 ms |
84844 KB |
Output is correct |
3 |
Execution timed out |
1041 ms |
16544 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
596 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Incorrect |
1 ms |
484 KB |
2nd lines differ - on the 1st token, expected: '25', found: '42' |
19 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
596 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Incorrect |
1 ms |
484 KB |
2nd lines differ - on the 1st token, expected: '25', found: '42' |
19 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |