#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200'001;
vector<pair<int,long long>> grafo[MAXN];
long long dist[MAXN][2];
void dfs(int nodo,int last,long long val,int mode){
dist[nodo][mode]=val;
for(auto [to,cost] : grafo[nodo]){
if(to!=last){
dfs(to,nodo,val+cost,mode);
}
}
}
bool a[MAXN][2],due[MAXN];
bool dfs2(int nodo,int last,int mode){
bool flag=due[nodo];
for(auto [i,cost] : grafo[nodo]){
if(i!=last){
flag|=dfs2(i,nodo,mode);
}
}
if(flag)a[nodo][mode]=true;
return flag;
}
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
for(int i=0;i<=N;i++)grafo[i].clear();
for(int i=0;i<N-1;i++){
grafo[U[i]].push_back({V[i],W[i]});
grafo[V[i]].push_back({U[i],W[i]});
}
if(X>Y)swap(X,Y);
dfs(X,-1,0,0);
dfs(Y,-1,0,1);
/*
int ans=0;
vector<long long> opz;
for(int i=0;i<N;i++){
opz.push_back(min(dist[i][0],dist[i][1]));
}
sort(opz.begin(),opz.end());
long long tmp = K;
for(int i=0;i<opz.size();i++){
if(tmp>=opz[i]){
ans++;
tmp-=opz[i];
}else break;
}
for(int l=0;l<N;l++){
for(int r=l;r<N;r++){
long long curr=0;
for(int i=l;i<=r;i++){
curr+=max(dist[i][0],dist[i][1]);
}
for(int i=X;i<l;i++){
curr+=dist[i][0];
}
for(int i=r+1;i<=Y;i++){
curr+=dist[i][1];
}
int ind1=min(X-1,l-1),ind2=max(Y+1,r+1);
long long tmp = K-curr;
//cout<<l<<" "<<r<<" "<<tmp<<"\n";
if(tmp<0)continue;
while((ind1>=0 && dist[ind1][0]<=tmp) || (ind2<N && dist[ind2][1]<=tmp)){
if(ind1<0){
tmp-=dist[ind2][1];
ind2++;
}else if(ind2>=N){
tmp-=dist[ind1][0];
ind1--;
}else if(dist[ind1][0]<dist[ind2][1]){
tmp-=dist[ind1][0];
ind1--;
}else{
tmp-=dist[ind2][1];
ind2++;
}
}
ans=max(ans,ind2-ind1-1+(r-l+1));
}
}
return ans;
*/
int ans=0;
for(int i=(1<<N)-1;i>=0;i--){
memset(a,false,sizeof(a));
memset(due,false,sizeof(due));
long long s=0;
int cc=0;
for(int j=0;j<N;j++){
if(i&(1<<j)){
due[j]=true;
s+=max(dist[j][0],dist[j][1]);
cc+=2;
}else cc++;
}
if(s>K || cc<ans)continue;
dfs2(X,-1,0);
dfs2(Y,-1,1);
long long tmp = K;
int curr=0;
vector<long long> opz;
for(int j=0;j<N;j++){
if(a[j][0] && a[j][1]){
tmp-=max(dist[j][0],dist[j][1]);
curr+=2;
}else if(a[j][0]){
tmp-=dist[j][0];
curr++;
}else if(a[j][1]){
tmp-=dist[j][1];
curr++;
}else{
opz.push_back(min(dist[j][0],dist[j][1]));
}
if(tmp<0)break;
}
sort(opz.begin(),opz.end());
if(tmp<0)continue;
for(int j=0;j<opz.size();j++){
if(tmp>=opz[j]){
tmp-=opz[j];
curr++;
}
}
ans=max(ans,curr);
}
return ans;
/*
vector<long long> opz;
for(int i=0;i<N;i++){
opz.push_back(min(dist[i][0],dist[i][1]));
}
sort(opz.begin(),opz.end());
int ans=0;
for(int i=0;i<opz.size();i++){
if(K>=opz[i]){
ans++;
K-=opz[i];
}else break;
}
return ans;*/
}
/*
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
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;
}
*/
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:143:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | for(int j=0;j<opz.size();j++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
136 ms |
31292 KB |
Output is correct |
| 2 |
Correct |
145 ms |
37436 KB |
Output is correct |
| 3 |
Correct |
505 ms |
8236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5588 KB |
Output is correct |
| 2 |
Execution timed out |
1063 ms |
5460 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5588 KB |
Output is correct |
| 2 |
Execution timed out |
1063 ms |
5460 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5588 KB |
Output is correct |
| 2 |
Execution timed out |
1063 ms |
5460 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5588 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5588 KB |
Output is correct |
| 3 |
Execution timed out |
1063 ms |
5460 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5588 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5588 KB |
Output is correct |
| 3 |
Execution timed out |
1063 ms |
5460 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5588 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5588 KB |
Output is correct |
| 3 |
Execution timed out |
1063 ms |
5460 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5588 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5588 KB |
Output is correct |
| 3 |
Execution timed out |
1063 ms |
5460 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5588 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5588 KB |
Output is correct |
| 3 |
Execution timed out |
1063 ms |
5460 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
