#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
struct edge{
int first;
long long second;
int previ;
};
vector <vector<edge> > adj;
long long check[200003];
long long Cost1[200003];
long long Cost2[200003];
long long DistX[200003];
long long DistY[200003];
long long BFSCheck[200003];
long long CPrev[200003];
long long N,X,Y,K,n;
long long ans1,ans2;
vector <int> XYPath;
int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
int n=N;
int x=X;
int y=Y;
long long k=K;
long long len;
long long Budget;
long long tans;
int s,e;
vector <edge> vtemp;
priority_queue <pair <long long,int> > pq;
vector <int> clist;
int cur;
int cur2;
adj.clear();
n=N;
XYPath.clear();
while(!pq.empty()){
pq.pop();
}
for(int i=0;i<=n+1;i++){
adj.push_back(vtemp);
check[i]=0;
Cost1[i]=0;
Cost2[i]=0;
DistX[i]=0;
DistY[i]=0;
}
ans1=0;
ans2=0;
for(int i=0;i<n-1;i++){
s=U[i];
e=V[i];
len=W[i];
adj[s].push_back({e,len});
adj[e].push_back({s,len});
}
//BFS tu X
for(int i=0;i<n;i++){
CPrev[i]=-1;
BFSCheck[i]=0;
}
cur=0;
clist.clear();
clist.push_back(X);
DistX[X]=0;
BFSCheck[X]=1;
while(cur<clist.size()){
for(int i=0;i<adj[clist[cur]].size();i++){
if(BFSCheck[adj[clist[cur]][i].first]==0){
BFSCheck[adj[clist[cur]][i].first]=1;
DistX[adj[clist[cur]][i].first]=DistX[clist[cur]]+adj[clist[cur]][i].second;
clist.push_back(adj[clist[cur]][i].first);
CPrev[adj[clist[cur]][i].first]=clist[cur];
}
}
//Tim duong di tu X den Y
if(clist[cur]==Y){
cur2=Y;
while(CPrev[cur2]!=-1){
XYPath.push_back(cur2);
cur2=CPrev[cur2];
}
XYPath.push_back(X);
}
cur++;
}
//BFS tu Y
for(int i=0;i<n;i++){
check[i]=0;
BFSCheck[i]=0;
}
cur=0;
clist.clear();
clist.push_back(Y);
DistY[Y]=0;
BFSCheck[Y]=1;
while(cur<clist.size()){
for(int i=0;i<adj[clist[cur]].size();i++){
if(BFSCheck[adj[clist[cur]][i].first]==0){
BFSCheck[adj[clist[cur]][i].first]=1;
DistY[adj[clist[cur]][i].first]=DistY[clist[cur]]+adj[clist[cur]][i].second;
clist.push_back(adj[clist[cur]][i].first);
CPrev[adj[clist[cur]][i].first]=clist[cur];
}
}
cur++;
}
//initialize 2 mang Cost1 va Cost2
for(int i=0;i<n;i++){
Cost1[i]=min(DistX[i],DistY[i]);
Cost2[i]=max(DistX[i],DistY[i])-Cost1[i];
}
//Case 1: Chi nang cap cac dinh len loai 1
for(int i=0;i<n;i++){
pq.push({-Cost1[i],0});
}
Budget=K;
ans1=0;
while(Budget>=0&&!pq.empty()){
Budget+=pq.top().first;
ans1++;
pq.pop();
}
if(Budget<0){
ans1--;
}
//Case2: Ton tai it nhat 1 dinh duoc nang cap len loai 2
while(!pq.empty()){
pq.pop();
}
Budget=K;
ans2=0;
for(int i=0;i<n;i++){
check[i]=0;
}
for(int i=0;i<XYPath.size();i++){
Budget-=Cost1[XYPath[i]];
check[XYPath[i]]=1;
ans2++;
}
if(Budget>0){
for(int i=0;i<n;i++){
if(check[i]==0){
pq.push({-Cost1[i],i});
}else{
pq.push({-Cost2[i],i});
}
}
while(!pq.empty()&&Budget>0){
Budget+=pq.top().first;
if(Budget>=0){
ans2++;
cur=pq.top().second;
pq.pop();
check[cur]++;
if(check[cur]==1){
pq.push({-Cost2[cur],cur});
}
}
}
}
tans=max(ans1,ans2);
return tans;
}
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:68:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | while(cur<clist.size()){
| ~~~^~~~~~~~~~~~~
closing.cpp:69:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int i=0;i<adj[clist[cur]].size();i++){
| ~^~~~~~~~~~~~~~~~~~~~~~~
closing.cpp:98:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | while(cur<clist.size()){
| ~~~^~~~~~~~~~~~~
closing.cpp:99:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int i=0;i<adj[clist[cur]].size();i++){
| ~^~~~~~~~~~~~~~~~~~~~~~~
closing.cpp:137:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for(int i=0;i<XYPath.size();i++){
| ~^~~~~~~~~~~~~~
closing.cpp:23:6: warning: unused variable 'x' [-Wunused-variable]
23 | int x=X;
| ^
closing.cpp:24:6: warning: unused variable 'y' [-Wunused-variable]
24 | int y=Y;
| ^
closing.cpp:25:12: warning: unused variable 'k' [-Wunused-variable]
25 | long long k=K;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10584 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 |
126 ms |
44636 KB |
1st lines differ - on the 1st token, expected: '451', found: '68601' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 2 |
Correct |
1 ms |
10584 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 4 |
Correct |
1 ms |
10588 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
10584 KB |
1st lines differ - on the 1st token, expected: '3', found: '16' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 2 |
Correct |
1 ms |
10584 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 4 |
Correct |
1 ms |
10588 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
10584 KB |
1st lines differ - on the 1st token, expected: '3', found: '16' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 2 |
Correct |
1 ms |
10584 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 4 |
Correct |
1 ms |
10588 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
10584 KB |
1st lines differ - on the 1st token, expected: '3', found: '16' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10584 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 |
2 ms |
10584 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 |
2 ms |
10584 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 |
2 ms |
10584 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 |
2 ms |
10584 KB |
2nd lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
