#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
long long Type[200003];
long long Check[200003];
long long BFSCheck[200003];
long long Cost1[200003];
long long Cost2[200003];
long long CPrev[200003];
long long DistX[200003];
long long DistY[200003];
long long check[200003];
long long N,X,Y,K,n,ans1,ans2;
struct edge{
int first;
long long second;
};
vector <edge> VTemp;
vector <vector <edge> > adj;
vector <int> XYPath;
priority_queue <pair <long long,int> > pq1,pq2,pq3;
priority_queue <long long> pq4;
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;
int q,s,e;
long long tans,Budget,len;
vector <int> CList;
int cur,cur2;
int t;
long long t2;
pair <long long,int> tpos;
while(!pq1.empty()){
pq1.pop();
}
while(!pq2.empty()){
pq2.pop();
}
while(!pq3.empty()){
pq3.pop();
}
while(!pq4.empty()){
pq4.pop();
}
XYPath.clear();
cin>>N>>X>>Y>>K;
adj.clear();
n=N;
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;
Type[i]=0;
}
ans1=0;
ans2=0;
for(int i=1;i<n;i++){
cin>>s>>e>>len;
adj[s].push_back({e,len});
adj[e].push_back({s,len});
}
CList.clear();
cur=0;
cur2=0;
for(int i=0;i<=n+1;i++){
BFSCheck[i]=0;
CPrev[i]=0;
}
CList.push_back(X);
BFSCheck[X]=1;
DistX[X]=0;
CPrev[X]=-1;
while(cur<CList.size()){
t=CList[cur];
for(int i=0;i<adj[t].size();i++){
if(BFSCheck[adj[t][i].first]==0){
BFSCheck[adj[t][i].first]=1;
DistX[adj[t][i].first]=DistX[t]+adj[t][i].second;
CPrev[adj[t][i].first]=t;
CList.push_back(adj[t][i].first);
if(adj[t][i].first==Y){
XYPath.push_back(Y);
cur2=Y;
while(CPrev[cur2]>=0){
cur2=CPrev[cur2];
XYPath.push_back(cur2);
}
}
}
}
cur++;
}
CList.clear();
cur=0;
cur2=0;
for(int i=0;i<=n+1;i++){
BFSCheck[i]=0;
CPrev[i]=0;
}
CList.push_back(Y);
BFSCheck[Y]=1;
DistY[Y]=0;
while(cur<CList.size()){
t=CList[cur];
for(int i=0;i<adj[t].size();i++){
if(BFSCheck[adj[t][i].first]==0){
BFSCheck[adj[t][i].first]=1;
DistY[adj[t][i].first]=DistY[t]+adj[t][i].second;
CList.push_back(adj[t][i].first);
}
}
cur++;
}
for(int i=0;i<n;i++){
Cost1[i]=min(DistX[i],DistY[i]);
Cost2[i]=max(DistX[i],DistY[i])-Cost1[i];
if(Cost2[i]<=Cost1[i]){
Type[i]=1;
}
}
for(int i=0;i<XYPath.size();i++){
Type[XYPath[i]]=2;
}
for(int i=0;i<n;i++){
pq4.push(-Cost1[i]);
}
Budget=K;
while(Budget>0&&!pq4.empty()){
Budget+=pq4.top();
if(Budget>=0){
ans1++;
pq4.pop();
}
}
Budget=K;
for(int i=0;i<XYPath.size();i++){
Budget-=Cost1[XYPath[i]];
check[XYPath[i]]=1;
ans2++;
}
tans=ans1;
if(Budget>0){
for(int i=0;i<n;i++){
if(Type[i]==0){
pq1.push({-Cost1[i],i});
pq1.push({-Cost2[i],i});
}else if(Type[i]==1){
pq2.push({-(Cost1[i]+Cost2[i]),i});
pq3.push({-Cost1[i],i});
}else{
pq1.push({-Cost2[i],i});
}
}
while(!pq2.empty()&&Budget+pq2.top().first>0){
if(pq1.size() <=1){
Budget+=pq2.top().first;
if(Budget>=0){
check[pq2.top().second]=2;
pq2.pop();
ans2+=2;
continue;
}
}
tpos=pq1.top();
pq1.pop();
if(pq1.top().first+tpos.first> pq2.top().first&&Budget+tpos.first>=0){
Budget+=(tpos.first);
ans2+=1;
check[tpos.second]++;
}else if(pq2.top().first+Budget>=0){
Budget+=pq2.top().first;
pq1.push(tpos);
ans2+=2;
check[pq2.top().second]=2;
pq2.pop();
}
}
while(!pq1.empty()&&Budget+pq1.top().first>=0){
Budget+=pq1.top().first;
ans2++;
check[pq1.top().second]++;
pq1.pop();
}
while(!pq3.empty()&&check[pq3.top().second]!=0){
pq3.pop();
}
if(!pq3.empty()&&pq3.top().first+Budget>=0){
ans2++;
check[pq3.top().second]=1;
}
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:79:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | while(cur<CList.size()){
| ~~~^~~~~~~~~~~~~
closing.cpp:81:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for(int i=0;i<adj[t].size();i++){
| ~^~~~~~~~~~~~~~
closing.cpp:109:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | while(cur<CList.size()){
| ~~~^~~~~~~~~~~~~
closing.cpp:111:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(int i=0;i<adj[t].size();i++){
| ~^~~~~~~~~~~~~~
closing.cpp:127:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for(int i=0;i<XYPath.size();i++){
| ~^~~~~~~~~~~~~~
closing.cpp:142:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for(int i=0;i<XYPath.size();i++){
| ~^~~~~~~~~~~~~~
closing.cpp:26:6: warning: unused variable 'x' [-Wunused-variable]
26 | int x=X;
| ^
closing.cpp:27:6: warning: unused variable 'y' [-Wunused-variable]
27 | int y=Y;
| ^
closing.cpp:28:12: warning: unused variable 'k' [-Wunused-variable]
28 | long long k=K;
| ^
closing.cpp:29:6: warning: unused variable 'q' [-Wunused-variable]
29 | int q,s,e;
| ^
closing.cpp:34:12: warning: unused variable 't2' [-Wunused-variable]
34 | long long t2;
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
11 ms |
21340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
101 ms |
45648 KB |
1st lines differ - on the 1st token, expected: '451', found: '400000' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
10588 KB |
1st lines differ - on the 1st token, expected: '3', found: '6' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
10588 KB |
1st lines differ - on the 1st token, expected: '3', found: '6' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
10588 KB |
1st lines differ - on the 1st token, expected: '3', found: '6' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
11 ms |
21340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
11 ms |
21340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
11 ms |
21340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
11 ms |
21340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
11 ms |
21340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
