#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
using vi = vector<int>;
using ll = long long;
const int maxn = 5e5 + 10;
const ll inf = 1e18 + 100;
vector<pair<int,ll>> g[maxn];
vector<int> path;
bool inpath[maxn];
ll dis[maxn];
bool fpath(int x,int p,int t) {
if(x==t){
path.push_back(x);
return true;
}
for(auto [y,w] : g[x]) if(y!=p) {
dis[y] = dis[x] + w;
if(fpath(y,x,t)){
path.push_back(x);
return true;
}
}
return false;
}
int vis[maxn];
int max_score(int n, int x, int y, long long k,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
// cerr << endl;
for(int i=0;i<n;i++) g[i].clear(),inpath[i]=vis[i]=dis[i]=0;
path.clear();
for(int i=0;i<U.size();i++){
g[U[i]].push_back({V[i],W[i]});
g[V[i]].push_back({U[i],W[i]});
}
fpath(x,x,y);
reverse(all(path));
for(int a : path)inpath[a]=1;
ll D = dis[y];
struct Choice {
ll d;
int a;
bool sec;
bool operator<(const Choice &o) const {return d>o.d;}
};
vector<ll> costt;
priority_queue<Choice> pq;
for(auto [a,w] : g[x]) if(!inpath[a]) {
pq.push({w,a,0});
}
for(auto [a,w] : g[y]) if(!inpath[a]) {
pq.push({w,a,0});
}
while(pq.size()) {
auto [d,a,sec] = pq.top();
pq.pop();
vis[a]=1;
costt.push_back(d);
if(sec)continue;
pq.push({D,a,1});
for(auto [b,w] : g[a])if(!inpath[b]&&!vis[b]){
pq.push({d+w,b,0});
}
}
vector<ll> costl;
pq.push({0,x,0});
pq.push({0,y,0});
while(pq.size()) {
auto [d,a,s] = pq.top();
pq.pop();
if(vis[a])continue;
vis[a]=1;
costl.push_back(d);
for(auto [b,w] : g[a]) if(inpath[b]&&!vis[b]){
pq.push({d+w,b,0});
}
}
// cerr << costl.size() << endl;
vector<ll> cost2;
for(int a : path) {
cost2.push_back(abs(dis[a]-(D-dis[a])));
}
sort(all(cost2));
for(ll x : cost2) costl.push_back(x);
int ans = 0;
ll sum = 0;
for(int i=0;i<costl.size();i++)sum+=costl[i];
// cerr << costl.size() << " " << costt.size() << endl;
for(int i=-1,j=(int)costl.size()-1;i<(int)costt.size();i++){
while(sum>k&&j>=0){
sum-=costl[j];
j--;
// cerr << sum << j << endl;
}
// cerr << "ij " << i << " " << j << endl;
if(sum<=k)ans=max(ans,(i+1)+(j+1));
if(i==(int)costt.size()-1)break;
sum+=costt[i+1];
}
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:37:55: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
37 | for(int i=0;i<n;i++) g[i].clear(),inpath[i]=vis[i]=dis[i]=0;
| ~~~~~~^~~~~~~~~
closing.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i=0;i<U.size();i++){
| ~^~~~~~~~~
closing.cpp:98:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(int i=0;i<costl.size();i++)sum+=costl[i];
| ~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
16220 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
93 ms |
40688 KB |
1st lines differ - on the 1st token, expected: '451', found: '264' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
16220 KB |
Output is correct |
2 |
Correct |
3 ms |
16220 KB |
Output is correct |
3 |
Correct |
4 ms |
16220 KB |
Output is correct |
4 |
Correct |
3 ms |
16328 KB |
Output is correct |
5 |
Correct |
4 ms |
16216 KB |
Output is correct |
6 |
Correct |
3 ms |
16220 KB |
Output is correct |
7 |
Correct |
4 ms |
16220 KB |
Output is correct |
8 |
Correct |
3 ms |
16220 KB |
Output is correct |
9 |
Correct |
3 ms |
16220 KB |
Output is correct |
10 |
Correct |
3 ms |
16220 KB |
Output is correct |
11 |
Correct |
3 ms |
16220 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
16220 KB |
Output is correct |
2 |
Correct |
3 ms |
16220 KB |
Output is correct |
3 |
Correct |
4 ms |
16220 KB |
Output is correct |
4 |
Correct |
3 ms |
16328 KB |
Output is correct |
5 |
Correct |
4 ms |
16216 KB |
Output is correct |
6 |
Correct |
3 ms |
16220 KB |
Output is correct |
7 |
Correct |
4 ms |
16220 KB |
Output is correct |
8 |
Correct |
3 ms |
16220 KB |
Output is correct |
9 |
Correct |
3 ms |
16220 KB |
Output is correct |
10 |
Correct |
3 ms |
16220 KB |
Output is correct |
11 |
Correct |
3 ms |
16220 KB |
Output is correct |
12 |
Correct |
3 ms |
16220 KB |
Output is correct |
13 |
Correct |
3 ms |
16220 KB |
Output is correct |
14 |
Correct |
3 ms |
16220 KB |
Output is correct |
15 |
Correct |
4 ms |
16220 KB |
Output is correct |
16 |
Correct |
3 ms |
16216 KB |
Output is correct |
17 |
Correct |
4 ms |
16316 KB |
Output is correct |
18 |
Correct |
3 ms |
16220 KB |
Output is correct |
19 |
Correct |
3 ms |
16324 KB |
Output is correct |
20 |
Correct |
4 ms |
16216 KB |
Output is correct |
21 |
Correct |
4 ms |
16220 KB |
Output is correct |
22 |
Correct |
3 ms |
16220 KB |
Output is correct |
23 |
Correct |
3 ms |
16220 KB |
Output is correct |
24 |
Correct |
3 ms |
16220 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
16220 KB |
Output is correct |
2 |
Correct |
3 ms |
16220 KB |
Output is correct |
3 |
Correct |
4 ms |
16220 KB |
Output is correct |
4 |
Correct |
3 ms |
16328 KB |
Output is correct |
5 |
Correct |
4 ms |
16216 KB |
Output is correct |
6 |
Correct |
3 ms |
16220 KB |
Output is correct |
7 |
Correct |
4 ms |
16220 KB |
Output is correct |
8 |
Correct |
3 ms |
16220 KB |
Output is correct |
9 |
Correct |
3 ms |
16220 KB |
Output is correct |
10 |
Correct |
3 ms |
16220 KB |
Output is correct |
11 |
Correct |
3 ms |
16220 KB |
Output is correct |
12 |
Correct |
3 ms |
16220 KB |
Output is correct |
13 |
Correct |
3 ms |
16220 KB |
Output is correct |
14 |
Correct |
3 ms |
16220 KB |
Output is correct |
15 |
Correct |
4 ms |
16220 KB |
Output is correct |
16 |
Correct |
3 ms |
16216 KB |
Output is correct |
17 |
Correct |
4 ms |
16316 KB |
Output is correct |
18 |
Correct |
3 ms |
16220 KB |
Output is correct |
19 |
Correct |
3 ms |
16324 KB |
Output is correct |
20 |
Correct |
4 ms |
16216 KB |
Output is correct |
21 |
Correct |
4 ms |
16220 KB |
Output is correct |
22 |
Correct |
3 ms |
16220 KB |
Output is correct |
23 |
Correct |
3 ms |
16220 KB |
Output is correct |
24 |
Correct |
3 ms |
16220 KB |
Output is correct |
25 |
Correct |
4 ms |
16220 KB |
Output is correct |
26 |
Correct |
5 ms |
16732 KB |
Output is correct |
27 |
Correct |
5 ms |
16740 KB |
Output is correct |
28 |
Correct |
4 ms |
16732 KB |
Output is correct |
29 |
Correct |
5 ms |
16732 KB |
Output is correct |
30 |
Correct |
4 ms |
16476 KB |
Output is correct |
31 |
Correct |
6 ms |
16772 KB |
Output is correct |
32 |
Correct |
4 ms |
16732 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
16220 KB |
Output is correct |
2 |
Correct |
4 ms |
16220 KB |
Output is correct |
3 |
Correct |
3 ms |
16220 KB |
Output is correct |
4 |
Correct |
4 ms |
16220 KB |
Output is correct |
5 |
Correct |
3 ms |
16328 KB |
Output is correct |
6 |
Correct |
4 ms |
16216 KB |
Output is correct |
7 |
Incorrect |
3 ms |
16220 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
16220 KB |
Output is correct |
2 |
Correct |
4 ms |
16220 KB |
Output is correct |
3 |
Correct |
3 ms |
16220 KB |
Output is correct |
4 |
Correct |
4 ms |
16220 KB |
Output is correct |
5 |
Correct |
3 ms |
16328 KB |
Output is correct |
6 |
Correct |
4 ms |
16216 KB |
Output is correct |
7 |
Correct |
3 ms |
16220 KB |
Output is correct |
8 |
Correct |
4 ms |
16220 KB |
Output is correct |
9 |
Correct |
3 ms |
16220 KB |
Output is correct |
10 |
Correct |
3 ms |
16220 KB |
Output is correct |
11 |
Correct |
3 ms |
16220 KB |
Output is correct |
12 |
Correct |
3 ms |
16220 KB |
Output is correct |
13 |
Correct |
3 ms |
16220 KB |
Output is correct |
14 |
Correct |
3 ms |
16220 KB |
Output is correct |
15 |
Correct |
3 ms |
16220 KB |
Output is correct |
16 |
Correct |
4 ms |
16220 KB |
Output is correct |
17 |
Correct |
3 ms |
16216 KB |
Output is correct |
18 |
Correct |
4 ms |
16316 KB |
Output is correct |
19 |
Incorrect |
3 ms |
16220 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
20 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
16220 KB |
Output is correct |
2 |
Correct |
4 ms |
16220 KB |
Output is correct |
3 |
Correct |
3 ms |
16220 KB |
Output is correct |
4 |
Correct |
4 ms |
16220 KB |
Output is correct |
5 |
Correct |
3 ms |
16328 KB |
Output is correct |
6 |
Correct |
4 ms |
16216 KB |
Output is correct |
7 |
Correct |
3 ms |
16220 KB |
Output is correct |
8 |
Correct |
4 ms |
16220 KB |
Output is correct |
9 |
Correct |
3 ms |
16220 KB |
Output is correct |
10 |
Correct |
3 ms |
16220 KB |
Output is correct |
11 |
Correct |
3 ms |
16220 KB |
Output is correct |
12 |
Correct |
3 ms |
16220 KB |
Output is correct |
13 |
Correct |
3 ms |
16220 KB |
Output is correct |
14 |
Correct |
3 ms |
16220 KB |
Output is correct |
15 |
Correct |
3 ms |
16220 KB |
Output is correct |
16 |
Correct |
4 ms |
16220 KB |
Output is correct |
17 |
Correct |
3 ms |
16216 KB |
Output is correct |
18 |
Correct |
4 ms |
16316 KB |
Output is correct |
19 |
Correct |
3 ms |
16220 KB |
Output is correct |
20 |
Correct |
3 ms |
16324 KB |
Output is correct |
21 |
Correct |
4 ms |
16216 KB |
Output is correct |
22 |
Correct |
4 ms |
16220 KB |
Output is correct |
23 |
Correct |
3 ms |
16220 KB |
Output is correct |
24 |
Correct |
3 ms |
16220 KB |
Output is correct |
25 |
Correct |
3 ms |
16220 KB |
Output is correct |
26 |
Incorrect |
3 ms |
16220 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
27 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
16220 KB |
Output is correct |
2 |
Correct |
4 ms |
16220 KB |
Output is correct |
3 |
Correct |
3 ms |
16220 KB |
Output is correct |
4 |
Correct |
4 ms |
16220 KB |
Output is correct |
5 |
Correct |
3 ms |
16328 KB |
Output is correct |
6 |
Correct |
4 ms |
16216 KB |
Output is correct |
7 |
Correct |
3 ms |
16220 KB |
Output is correct |
8 |
Correct |
4 ms |
16220 KB |
Output is correct |
9 |
Correct |
3 ms |
16220 KB |
Output is correct |
10 |
Correct |
3 ms |
16220 KB |
Output is correct |
11 |
Correct |
3 ms |
16220 KB |
Output is correct |
12 |
Correct |
3 ms |
16220 KB |
Output is correct |
13 |
Correct |
3 ms |
16220 KB |
Output is correct |
14 |
Correct |
3 ms |
16220 KB |
Output is correct |
15 |
Correct |
3 ms |
16220 KB |
Output is correct |
16 |
Correct |
4 ms |
16220 KB |
Output is correct |
17 |
Correct |
3 ms |
16216 KB |
Output is correct |
18 |
Correct |
4 ms |
16316 KB |
Output is correct |
19 |
Correct |
3 ms |
16220 KB |
Output is correct |
20 |
Correct |
3 ms |
16324 KB |
Output is correct |
21 |
Correct |
4 ms |
16216 KB |
Output is correct |
22 |
Correct |
4 ms |
16220 KB |
Output is correct |
23 |
Correct |
3 ms |
16220 KB |
Output is correct |
24 |
Correct |
3 ms |
16220 KB |
Output is correct |
25 |
Correct |
3 ms |
16220 KB |
Output is correct |
26 |
Correct |
4 ms |
16220 KB |
Output is correct |
27 |
Correct |
5 ms |
16732 KB |
Output is correct |
28 |
Correct |
5 ms |
16740 KB |
Output is correct |
29 |
Correct |
4 ms |
16732 KB |
Output is correct |
30 |
Correct |
5 ms |
16732 KB |
Output is correct |
31 |
Correct |
4 ms |
16476 KB |
Output is correct |
32 |
Correct |
6 ms |
16772 KB |
Output is correct |
33 |
Correct |
4 ms |
16732 KB |
Output is correct |
34 |
Incorrect |
3 ms |
16220 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
35 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
16220 KB |
Output is correct |
2 |
Correct |
4 ms |
16220 KB |
Output is correct |
3 |
Correct |
3 ms |
16220 KB |
Output is correct |
4 |
Correct |
4 ms |
16220 KB |
Output is correct |
5 |
Correct |
3 ms |
16328 KB |
Output is correct |
6 |
Correct |
4 ms |
16216 KB |
Output is correct |
7 |
Correct |
3 ms |
16220 KB |
Output is correct |
8 |
Correct |
4 ms |
16220 KB |
Output is correct |
9 |
Correct |
3 ms |
16220 KB |
Output is correct |
10 |
Correct |
3 ms |
16220 KB |
Output is correct |
11 |
Correct |
3 ms |
16220 KB |
Output is correct |
12 |
Correct |
3 ms |
16220 KB |
Output is correct |
13 |
Correct |
3 ms |
16220 KB |
Output is correct |
14 |
Correct |
3 ms |
16220 KB |
Output is correct |
15 |
Correct |
3 ms |
16220 KB |
Output is correct |
16 |
Correct |
4 ms |
16220 KB |
Output is correct |
17 |
Correct |
3 ms |
16216 KB |
Output is correct |
18 |
Correct |
4 ms |
16316 KB |
Output is correct |
19 |
Correct |
3 ms |
16220 KB |
Output is correct |
20 |
Correct |
3 ms |
16324 KB |
Output is correct |
21 |
Correct |
4 ms |
16216 KB |
Output is correct |
22 |
Correct |
4 ms |
16220 KB |
Output is correct |
23 |
Correct |
3 ms |
16220 KB |
Output is correct |
24 |
Correct |
3 ms |
16220 KB |
Output is correct |
25 |
Correct |
3 ms |
16220 KB |
Output is correct |
26 |
Correct |
4 ms |
16220 KB |
Output is correct |
27 |
Correct |
5 ms |
16732 KB |
Output is correct |
28 |
Correct |
5 ms |
16740 KB |
Output is correct |
29 |
Correct |
4 ms |
16732 KB |
Output is correct |
30 |
Correct |
5 ms |
16732 KB |
Output is correct |
31 |
Correct |
4 ms |
16476 KB |
Output is correct |
32 |
Correct |
6 ms |
16772 KB |
Output is correct |
33 |
Correct |
4 ms |
16732 KB |
Output is correct |
34 |
Incorrect |
3 ms |
16220 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
35 |
Halted |
0 ms |
0 KB |
- |