#include <bits/stdc++.h>
#include "closing.h"
using namespace std;
#define int long long
#define sz(a){ return (int)a.size(); }
const int INF=1e9;
vector<vector<pair<int,int>>> edges;
vector<int> dstX;
vector<int> dstY;
signed max_score(signed N, signed rootX, signed rootY, long long K, std::vector<signed> U, std::vector<signed> V, std::vector<signed> W){
vector<pair<int,int>> singl;
vector<pair<int,int>> doubl;
edges.clear();
dstX.clear();
edges.resize(N);
dstX.resize(N);
dstY.resize(N);
singl.resize(N);
doubl.resize(N);
for (int i = 0; i < N-1; i++)
{
edges[V[i]].push_back({U[i], W[i]});
edges[U[i]].push_back({V[i], W[i]});
}
vector<bool> visited(N);
queue<pair<int,int>> queue;
queue.push({rootX,0});
while(!queue.empty()){
int x=queue.front().first,w=queue.front().second; queue.pop();
if(visited[x]) continue;
visited[x]=true;
dstX[x]=w;
for (auto u: edges[x]) queue.push({u.first, u.second+w});
}
visited.clear();
visited.resize(N);
queue.push({rootY,0});
while(!queue.empty()){
int x=queue.front().first,w=queue.front().second; queue.pop();
if(visited[x]) continue;
visited[x]=true;
dstY[x]=w;
for (auto u: edges[x]) queue.push({u.first, u.second+w});
}
for (int i = 0; i < N; i++) singl[i]={min(dstY[i], dstX[i]),i};
for (int i = 0; i < N; i++) doubl[i]={max(dstY[i],dstX[i]), i};
int res=K;
int sum=0;
while(!singl.empty()){
sort(singl.begin(),singl.end()); // sort both
sort(doubl.begin(),doubl.end());
if(singl.size()==1||(res-(singl[0].first+singl[1].first)<0&&(doubl.empty()||(res-doubl[0].first)<0))){
if(res-singl[0].first>=0) sum++;
break;
}
if(doubl.empty() || singl[0].first+singl[1].first<doubl[0].first){
res-=singl[0].first+singl[1].first;
int a=-1,b=-1;
if(!doubl.empty()) {
for (int i = 0; i < doubl.size(); i++)
{
if(doubl[i].second==singl[0].second||doubl[i].second==singl[1].second) {
a=i;
swap(a,b);
}
}
}
if(b!=-1){
singl.push_back({max(dstY[doubl[b].second], dstX[doubl[b].second]),doubl[b].second});
doubl.erase(doubl.begin()+b);
if(b<a) a--;
if(a!=-1){
singl.push_back({max(dstY[doubl[a].second], dstX[doubl[a].second]),doubl[a].second});
doubl.erase(doubl.begin()+a);
}
}
cerr<<singl[0].second << " " << singl[1].second << "- used\n";
singl.erase(singl.begin());
singl.erase(singl.begin());
}else{
res-=doubl[0].first;
for (int i = 0; i < singl.size(); i++)
{
if(singl[i].second==doubl[0].second) { singl.erase(singl.begin()+i); break; }
}
cerr<<doubl[0].second << "- double used\n";
doubl.erase(doubl.begin());
}
sum+=2;
}
return (int)sum;
}
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:66:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for (int i = 0; i < doubl.size(); i++)
| ~~^~~~~~~~~~~~~~
closing.cpp:88:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for (int i = 0; i < singl.size(); i++)
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1051 ms |
33484 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
436 KB |
1st lines differ - on the 1st token, expected: '34', found: '32' |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
436 KB |
1st lines differ - on the 1st token, expected: '34', found: '32' |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
436 KB |
1st lines differ - on the 1st token, expected: '34', found: '32' |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
2nd 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 |
348 KB |
2nd 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 |
348 KB |
2nd 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 |
348 KB |
2nd 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 |
348 KB |
2nd lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
