Submission #851002

#	Time	Username	Problem	Language	Result	Execution time	Memory
851002		Lib	Closing Time (IOI23_closing)	C++17	100 / 100	199 ms	52424 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
int Type[200003];
int Check[200003];
int BFSCheck[200003];
long long Cost1[200003];
long long Cost2[200003];
long long dp[5003][10003];
int CPrev[200003];
long long DistX[200003];
long long DistY[200003];
int check[200003];
vector <int> VOrder1;
vector <int> VOrder2;
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,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();
		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++){
			s=U[i-1];
			e=V[i-1];
			len=W[i-1];
			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],i});
		}
		Budget=K;
		while(Budget>0&&!pq4.empty()){
			Budget+=pq4.top().first;
			if(Budget>=0){
				ans1++;
				VOrder1.push_back(pq4.top().second);
				pq4.pop();
			}
		}
		Budget=K;
		for(int i=0;i<XYPath.size();i++){
			Budget-=Cost1[XYPath[i]];
			check[XYPath[i]]=1;
			ans2++;
			VOrder2.push_back(XYPath[i]);
		}
		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;
					VOrder2.push_back(pq2.top().second);
					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]++;
					VOrder2.push_back(tpos.second);
				}else if(pq2.top().first+Budget>=0){
				Budget+=pq2.top().first;
					pq1.push(tpos);
					ans2+=2;
					check[pq2.top().second]=2;
					VOrder2.push_back(pq2.top().second);
					VOrder2.push_back(pq2.top().second);
					pq2.pop();
				}
			}
			while(!pq1.empty()&&Budget+pq1.top().first>=0){
				Budget+=pq1.top().first;
					ans2++;
					check[pq1.top().second]++;
					VOrder2.push_back(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;
				VOrder2.push_back(pq3.top().second);
			}
			tans=max(ans1,ans2);
		}
		return tans;
}

Compilation message (stderr)

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:82:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   while(cur<CList.size()){
      |         ~~~^~~~~~~~~~~~~
closing.cpp:84:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |    for(int i=0;i<adj[t].size();i++){
      |                ~^~~~~~~~~~~~~~
closing.cpp:112:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |   while(cur<CList.size()){
      |         ~~~^~~~~~~~~~~~~
closing.cpp:114:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |    for(int i=0;i<adj[t].size();i++){
      |                ~^~~~~~~~~~~~~~
closing.cpp:130:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |   for(int i=0;i<XYPath.size();i++){
      |               ~^~~~~~~~~~~~~~
closing.cpp:146:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |   for(int i=0;i<XYPath.size();i++){
      |               ~^~~~~~~~~~~~~~
closing.cpp:28:6: warning: unused variable 'x' [-Wunused-variable]
   28 |  int x=X;
      |      ^
closing.cpp:29:6: warning: unused variable 'y' [-Wunused-variable]
   29 |  int y=Y;
      |      ^
closing.cpp:30:12: warning: unused variable 'k' [-Wunused-variable]
   30 |  long long k=K;
      |            ^
closing.cpp:31:6: warning: unused variable 'q' [-Wunused-variable]
   31 |  int q,s,e;
      |      ^
closing.cpp:36:12: warning: unused variable 't2' [-Wunused-variable]
   36 |  long long t2;
      |            ^~

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 9 / 9
• Subtask 6: 11 / 11
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 17 / 17