#include "closing.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;
long long n,x,y,k;
vector<pair<long long,long long>> haha[200001];
vector<long long> bruh(200001);
vector<long long> wow(200001);
vector<pair<long long,long long>> idk(0);
void dfs(long long a, long long t, long long d, bool yeah) {
if(yeah) {
bruh[a] = d;
}
else {
wow[a] = d;
}
for(pair<long long,long long> v: haha[a]) {
if(v.first != t) {
dfs(v.first,a,d+v.second,yeah);
}
}
}
bool dude(long long a, long long t) {
if(a == y) {
if(bruh[a] < wow[a]) {
k-=bruh[a];
wow[a]-=bruh[a];
bruh[a] = 0;
}
else {
k-=wow[a];
bruh[a]-=wow[a];
wow[a] = 0;
}
return true;
}
for(pair<long long,long long> v: haha[a]) {
if(v.first != t) {
if(dude(v.first,a)) {
if(bruh[a] < wow[a]) {
k-=bruh[a];
wow[a]-=bruh[a];
bruh[a] = 0;
}
else {
k-=wow[a];
bruh[a]-=wow[a];
wow[a] = 0;
}
return true;
}
}
}
return false;
}
long long solve() {
long long sb = 0;
vector<int> ans(n+1,-1);
priority_queue<pair<long long,pair<long long,long long>>> no;
priority_queue<pair<long long,pair<long long,long long>>> rem;
priority_queue<pair<long long,long long>> dv;
no.push({-LLONG_MAX/3,{n,-1}});
rem.push({-LLONG_MAX/3,{n,-1}});
dv.push({-LLONG_MAX/3,-1});
for(int i = 0; i < n; i++) {
ans[i] = 0;
no.push({-idk[i].first,{i,0}});
dv.push({-idk[i].second,i});
}
for(int i = 0; i < 2*n; i++) {
while(ans[no.top().second.first] != no.top().second.second) {
no.pop();
}
while(ans[rem.top().second.first] != rem.top().second.second) {
rem.pop();
}
while(dv.top().second != -1 && ans[dv.top().second] != 0) {
dv.pop();
}
if(-dv.top().first-rem.top().first < -no.top().first) {
long long p1 = rem.top().second.first,p2 = dv.top().second,c = -dv.top().first-rem.top().first;
ans[p1]--;
ans[p2]+=2;
sb+=c;
rem.push({idk[p2].second,{p2,2}});
if(ans[p1] == 1) {
rem.push({idk[p1].first,{p1,1}});
no.push({-idk[p1].second,{p1,1}});
}
else {
no.push({-idk[p1].first,{p1,0}});
dv.push({-idk[p1].second,p1});
}
}
else {
ans[no.top().second.first]++;
long long c,p = no.top().second.first;
if(no.top().second.second == 1) {
c = idk[p].second;
}
else {
c = idk[p].first;
no.push({-idk[p].second,{p,ans[p]}});
}
sb+=c;
rem.push({c,{p,ans[p]}});
}
if(sb > k) {
return i;
}
}
return 2*n;
}
int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N;
x = X;
y = Y;
k = K;
for(int i = 0; i < n; i++) {
haha[i].clear();
}
for(long long i = 0; i < n-1; i++) {
haha[U[i]].push_back({V[i],W[i]});
haha[V[i]].push_back({U[i],W[i]});
}
long long ans = 0;
dfs(x,-1,0,true);
dfs(y,-1,0,false);
vector<long long> wut(n);
for(long long i = 0; i < n; i++) {
wut[i] = min(bruh[i],wow[i]);
}
sort(wut.begin(),wut.end());
long long sb = 0;
for(long long i = 0; i < wut.size(); i++) {
sb+=wut[i];
if(sb > k) {
break;
}
ans++;
}
dude(x,-1);
if(k < 0) {
return ans;
}
idk.clear();
for(int i = 0; i < n; i++) {
idk.push_back({min(bruh[i],wow[i]),max(bruh[i],wow[i])-min(bruh[i],wow[i])});
}
return max(solve(),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:140:28: 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]
140 | for(long long i = 0; i < wut.size(); i++) {
| ~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
8280 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
96 ms |
32596 KB |
Output is correct |
| 2 |
Correct |
104 ms |
37728 KB |
Output is correct |
| 3 |
Correct |
54 ms |
13392 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
8288 KB |
1st lines differ - on the 1st token, expected: '30', found: '40' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
8288 KB |
1st lines differ - on the 1st token, expected: '30', found: '40' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
8288 KB |
1st lines differ - on the 1st token, expected: '30', found: '40' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
8288 KB |
1st lines differ - on the 1st token, expected: '30', found: '40' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
8288 KB |
1st lines differ - on the 1st token, expected: '30', found: '40' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
8288 KB |
1st lines differ - on the 1st token, expected: '30', found: '40' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
8288 KB |
1st lines differ - on the 1st token, expected: '30', found: '40' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
8288 KB |
1st lines differ - on the 1st token, expected: '30', found: '40' |
| 4 |
Halted |
0 ms |
0 KB |
- |
