Submission #939321

#	Time	Username	Problem	Language	Result	Execution time	Memory
939321		WanWan	Closing Time (IOI23_closing)	C++17	29 / 100	1014 ms	12392 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
#define int long long
const int MAXN = 3005;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9+7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 
vector<pi>adj[MAXN];

int par[MAXN];
int dep[MAXN];

void dfs(int x, int p){
   	par[x]=p;
   	for(auto v:adj[x])if(v.first!=p){
   		dep[v.first]=dep[x]+1;
   		dfs(v.first,x);
   	}
}
int dd[2][MAXN];
void bfs(int src, int xx){
	queue<int> qu;
	memset(dd[xx],-1,sizeof dd[xx]);
	dd[xx][src]=0;
	qu.push(src);
	while(qu.size()){
		int c=qu.front();
		qu.pop();

		for(auto v:adj[c]){
			if(dd[xx][v.first] == -1 || dd[xx][v.first] > dd[xx][c]+v.second){
				dd[xx][v.first]=dd[xx][c]+v.second;
				qu.push(v.first);
			}
		}
	}
}
int32_t max_score(int32_t n, int32_t X, int32_t Y, long long K,
              std::vector<int32_t> U, std::vector<int32_t> V, std::vector<int32_t> W)
{
	for(int i=0;i<n;i++){
		adj[i].clear();
	}
    for(int i=0;i<n-1;i++){
        adj[U[i]].push_back({V[i],W[i]});
        adj[V[i]].push_back({U[i],W[i]});
    }
   	dfs(1,-1);
   	vector<int> v1,v2;
   	int x=X,y=Y;
   	while(x!=y){
   		if(dep[x]>dep[y]){
   			v1.push_back(x);
   			x=par[x];
   		} else{
   			v2.push_back(y);
   			y=par[y];
   		}
   	}

   	unordered_set<int> path;
   	reverse(v2.begin(),v2.end());
   	vector<int> vec;
   	for(auto e:v1)vec.push_back(e);
   	vec.push_back(x);
   	for(auto e:v2)vec.push_back(e);
   	for(auto e:vec)path.insert(e);
	int ans=2;
   	// 1. calc if there's 0 intersection--just greedily choose the cheapest node
	bfs(X,0);
	bfs(Y,1);

	{
		vector<int> vs;
		for(int i=0;i<n;i++)vs.push_back(dd[0][i]);
		for(int i=0;i<n;i++)vs.push_back(dd[1][i]);
		sort(vs.begin(),vs.end());
		int cst=0;
		int cc=0;
		for(auto x:vs){
			cst+=x;
			++cc;
			if(cst<=K){
				ans=max(ans,cc);
			} else{
				break;
			}
		}
	}
   	// 2. if there's at least 1 intersection, it'll happen on the path
   
   	
   	for(int i=0;i<vec.size();i++){

   		for(int j=i;j<vec.size();j++){

   			int cost = 0;
   			int cnt=0;
   			priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> one; //{cost,index,min/max}
   			priority_queue<pi,vector<pi>,greater<pi>> both;
   			for(int k=0;k<vec.size();k++){
   				if(k<i){
   					cost+=min(dd[1][vec[k]],dd[0][vec[k]]);
   					++cnt;
   				}
   				else if(k<=j){
   					cost+=max(dd[0][vec[k]],dd[1][vec[k]]);
   					cnt+=2;
   				}
   				else {
   					cost+=min(dd[1][vec[k]],dd[0][vec[k]]);
   					++cnt;
   				}
   			}

   			if(cost>K)continue;
   			ans=max(ans,cnt);
   			
   			for(int k=0;k<n;k++){
   				if(path.find(k) != path.end()){
					
   				} else{
   					both.push({max(dd[0][k],dd[1][k]),k});
					one.push({min(dd[0][k],dd[1][k]),k,0});
   				}
   			}
   			
   			set<pi>doneone;
   			set<int>doneboth;

   			while(true){
   				ans=max(ans,cnt);
   				// try taking 1 only
   				
   				while(one.size() && doneone.find({one.top()[1],one.top()[2]}) != doneone.end())one.pop();
   				if(one.size()){
   					if(cost+one.top()[0]<=K)ans=max(ans,cnt+1);
   				}

   				int c1=oo,c2=oo;

   				if(one.size()){

   					c1=0;
					array<int,3> cur=one.top();
					c1+=cur[0];

   					one.pop();
   					while(one.size() && doneone.find({one.top()[1],one.top()[2]}) != doneone.end())one.pop();
   					if(one.size())c1+=one.top()[0];
   					else c1=oo;
   					one.push(cur);
   				}
   				while(both.size() && doneboth.find(both.top().second) != doneboth.end())both.pop();
   				if(both.size()){
   					c2=both.top().first;
   				}
   				if(c2==oo && c1==oo)break;

   				if(c2<c1){ // we should take the smaller one of the both
   					assert(both.size());
   					pi cur=both.top();
   					cnt++;
   					cost += min(dd[0][cur.second],dd[1][cur.second]);
   					one.push({abs(dd[0][cur.second]-dd[1][cur.second]),cur.second,1});
   					doneone.insert({cur.second,0});
   					both.pop();
   				} else{

   					array<int,3>cur=one.top();
   					one.pop();
   					cnt++;
   					cost+=cur[0];
   					if(cur[2] == 0){ // push max
   						one.push({max(dd[0][cur[1]],dd[1][cur[1]])-cur[0],cur[1],1});
   						doneboth.insert(cur[1]);
   					}
   				}
   				if(cost<=K){
   					ans=max(ans,cnt);
   				} else{
   					break;
   				}

   			}
   			debug(i,j,ans);

   		}
   	}

   	return ans;
}

Compilation message (stderr)

closing.cpp: In function 'int32_t max_score(int32_t, int32_t, int32_t, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:104:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     for(int i=0;i<vec.size();i++){
      |                 ~^~~~~~~~~~~
closing.cpp:106:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |      for(int j=i;j<vec.size();j++){
      |                  ~^~~~~~~~~~~
closing.cpp:112:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |       for(int k=0;k<vec.size();k++){
      |                   ~^~~~~~~~~~~

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