Submission #842740

#	Time	Username	Problem	Language	Result	Execution time	Memory
842740		errorgorn	Closing Time (IOI23_closing)	C++17	100 / 100	583 ms	37064 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int INF=2e18;

int n,k;
vector<ii> al[200005];

int w[2][200005];

void dfs(int i,int p,int ww,int idx){
	w[idx][i]=ww;
	for (auto [it,www]:al[i]){
		if (it==p) continue;
		dfs(it,i,ww+www,idx);
	}
}

vector<int> s,b;
vector<int> ps,pb;
int banidx;

int gb(int i){
	if (banidx<=i) return b[i+1];
	else return b[i];
}

int gpb(int i){
	if (banidx<=i) return pb[i+1]-b[banidx];
	else return pb[i];
}

ii get(int v){
	ii res;
	
	int lo=0,hi=sz(s),mi;
	while (hi-lo>1){
		mi=hi+lo>>1;
		if (s[mi]<=v/2) lo=mi;
		else hi=mi;
	}
	
	res.fi=lo;
	
	lo=0,hi=sz(b)-(banidx!=INF),mi;
	while (hi-lo>1){
		mi=hi+lo>>1;
		if (gb(mi)<=v) lo=mi;
		else hi=mi;
	}
	
	res.se=lo;
	return res;
}

vector<int> V;

int get(int lim,int ban){
	if (lim<0) return -INF;
	if (ban==INF) banidx=INF;
	else banidx=lb(all(b),ban)-b.begin();
	
	//cout<<"debug: "<<lim<<" "<<ban<<endl;
	//rep(x,0,sz(s)) cout<<ps[x]<<" "; cout<<endl;
	//rep(x,0,sz(b)-1) cout<<gpb(x)<<" "; cout<<endl;
	
	int lo=0,hi=sz(V),mi;
	while (hi-lo>1){
		mi=hi+lo>>1;
		
		auto temp=get(V[mi]);
		if (ps[temp.fi]+gpb(temp.se)<=lim) lo=mi;
		else hi=mi;
	}
	
	hi=V[lo+1];
	lo=V[lo];
	auto t1=get(lo),t2=get(hi);
	
	int si=t1.fi,bi=t1.se;
	lim-=ps[si]+gpb(bi);
	
	int temp=min(lim/hi,t2.se-t1.se);
	lim-=temp*hi;
	bi+=temp;
	
	if (hi>=2){
		temp=min(lim/(hi/2),t2.fi-t1.fi);
		lim-=temp*(hi/2);
		si+=temp;
	}
	
	if (lim-s[si+1]>=0) return si+bi*2+1;
	if (lim+s[si]-gb(bi+1)>=0) return si+bi*2+1;
	return si+bi*2;
}

signed max_score(signed N, signed X, signed Y, int K,
              vector<signed> UU, vector<signed> VV, vector<signed> WW){
	
	n=N,k=K;
	
	rep(x,0,n) al[x].clear();
	s.clear(),b.clear();
	
	rep(x,0,n-1){
		al[UU[x]].pub({VV[x],WW[x]});
		al[VV[x]].pub({UU[x],WW[x]});
	}
	
	dfs(X,-1,0,0);
	dfs(Y,-1,0,1);
	
	rep(x,0,n){
		if (w[0][x]>w[1][x]) swap(w[0][x],w[1][x]);
		w[1][x]-=w[0][x];
	}
	
	//rep(x,0,n) cout<<w[0][x]<<" "; cout<<endl;
	//rep(x,0,n) cout<<w[1][x]<<" "; cout<<endl;
	
	vector<int> v;
	rep(x,0,n) v.pub(w[0][x]);
	sort(all(v));
	
	int ans=0,curr=0;
	while (ans<n && curr+v[ans]<=k) curr+=v[ans],ans++;
	
	int d=w[1][X],extra=0;
	rep(x,0,n){
		if (2*w[0][x]+w[1][x]==d){
			k-=w[0][x];
			s.pub(w[1][x]);
			extra++;
		}
		else if (w[0][x]<=w[1][x]) s.pub(w[0][x]),s.pub(w[1][x]);
		else b.pub(w[0][x]+w[1][x]);
	}
	
	s.pub(0),s.pub(INF);
	b.pub(0),b.pub(INF);
	sort(all(s));
	sort(all(b));
	
	V={0};
	for (auto it:s) V.pub(it*2);
	for (auto it:b) V.pub(it);
	sort(all(V));
	V.erase(unique(all(V)),V.end());
	
	//for (auto it:s) cout<<it<<" "; cout<<endl;
	//for (auto it:b) cout<<it<<" "; cout<<endl;
	//for (auto it:V) cout<<it<<" "; cout<<endl;
	
	ps=s,pb=b;
	rep(x,1,sz(ps)) ps[x]+=ps[x-1];
	rep(x,1,sz(pb)) pb[x]+=pb[x-1];
	
	ans=max(ans,extra+get(k,INF));
	rep(x,0,n) if (2*w[0][x]+w[1][x]!=d && w[0][x]>w[1][x]){
		ans=max(ans,extra+get(k-w[0][x],w[0][x]+w[1][x])+1);
	}
	
	return ans;
}

Compilation message (stderr)

closing.cpp: In function 'std::pair<long long int, long long int> get(long long int)':
closing.cpp:59:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |   mi=hi+lo>>1;
      |      ~~^~~
closing.cpp:66:32: warning: right operand of comma operator has no effect [-Wunused-value]
   66 |  lo=0,hi=sz(b)-(banidx!=INF),mi;
      |                                ^
closing.cpp:68:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |   mi=hi+lo>>1;
      |      ~~^~~
closing.cpp: In function 'long long int get(long long int, long long int)':
closing.cpp:90:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |   mi=hi+lo>>1;
      |      ~~^~~

• 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