Submission #939335

#	Time	Username	Problem	Language	Result	Execution time	Memory
939335		WanWan	Closing Time (IOI23_closing)	C++17	18 / 100	48 ms	10064 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);
			}
		}
	}
}
map<int,int>cst;
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;
			}
		}
	}
	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;
   	// 2. if there's at least 1 intersection, it'll happen on the path
   
   	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;
   	int cost=0;
   	int cnt=0;

   	while(true){
   		
   		// try taking 1 only
   		//cst[cost]=cnt;
   		while(one.size() && doneone.find({one.top()[1],one.top()[2]}) != doneone.end())one.pop();
   		if(one.size()){
   			cst[cnt+1]=cost+one.top()[0];
   			//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(cst.find(cnt) == cst.end())cst[cnt]=cost;
   		else cst[cnt]=min(cst[cnt],cost);
   	}
   	for(auto x:cst){
   		debug(x.first,x.second);
   	}
   	debug(__LINE__);
   			

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

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

   			int cost = 0;
   			int cnt=0;
   			
   			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(auto x:cst){
   				if(cost+x.second<=K){
   					ans=max(ans,cnt+x.first);
   				}
   			}
   		}
   			


   	}

   	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:171:14: warning: variable 'x' set but not used [-Wunused-but-set-variable]
  171 |     for(auto x:cst){
      |              ^
closing.cpp:177: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]
  177 |     for(int i=0;i<vec.size();i++){
      |                 ~^~~~~~~~~~~
closing.cpp:179: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]
  179 |      for(int j=i;j<vec.size();j++){
      |                  ~^~~~~~~~~~~
closing.cpp:184: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]
  184 |       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: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17