Submission #1132629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132629		Saul0906	Closing Time (IOI23_closing)	C++20	83 / 100	1096 ms	1135080 KiB

closing

//#include "closing.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repr(a,b,c) for(int a=b-1; a>c-1; a--)
#define repa(a,b) for(auto a:b)
#define pb push_back

using namespace std;
using ll = long long int;
using vi = vector<int>;
template<typename T>
using vec = vector<T>;
template<typename T>
using pq_min = priority_queue<T,vector<T>,greater<T>>;
using pii = pair<int, int>;
using iii = array<ll,3>;

const int N=3005, N2=2e5;
const ll inf=2e18;
ll dp[N][N*2][4], dp2[N][N*2][4], dis[3][N];
vec<pii> adj[N2];
int tin[N], tout[N], timer, sz[N];

void dfs(int u, int p){
	tin[u]=timer++;
	repa(v,adj[u]) if(v.fi!=p) dfs(v.fi,u);
	tout[u]=timer++;
}

void solve(int u, int p, int x, int y){
	sz[u]=1;
	dp[u][0][0]=0;
	dp[u][1][2]=dis[0][u];
	dp[u][1][1]=dis[1][u];
	dp[u][2][3]=dis[2][u];
	repa(e,adj[u]){
		int v=e.fi;
		if(v==p) continue;
		solve(v,u,x,y);
		vec<pii> vt;
		rep(mask,0,4){
			rep(mask2,0,4){
				if((mask2&2) && !(mask&2) && !(tin[v]<=tin[x] && tout[x]<=tout[v])) continue;
				if((mask2&1) && !(mask&1) && !(tin[v]<=tin[y] && tout[y]<=tout[v])) continue;
				if((mask&2) && !(mask2&2) && (tin[v]<=tin[x] && tout[x]<=tout[v])) continue;
				if((mask&1) && !(mask2&1) && (tin[v]<=tin[y] && tout[y]<=tout[v])) continue;
				vt.pb({mask,mask2});
			}
		}
		rep(j,0,2*sz[v]+1){
			repr(i,2*sz[u]+1,0){
				rep(k,0,(int)vt.size()){
					dp2[u][i+j][vt[k].fi]=min(dp2[u][i+j][vt[k].fi],dp[u][i][vt[k].fi]+dp[v][j][vt[k].se]);
				}
			}
		}
		sz[u]+=sz[v];
		rep(j,0,2*sz[u]+1) rep(mask,0,4) dp[u][j][mask]=dp2[u][j][mask], dp2[u][j][mask]=inf;
	}
}

int max_score(int n, int x, int y, ll k, vi u, vi v, vi w){
	rep(i,0,n) adj[i].clear();
	rep(i,0,n-1){
		adj[u[i]].pb({v[i],w[i]});
		adj[v[i]].pb({u[i],w[i]});
	}
	pq_min<iii> pq;
	pq.push({0,x,0});
	pq.push({0,y,1});
	int a, b, d;
	rep(i,0,n) dis[0][i]=dis[1][i]=inf;
	dis[0][x]=0;
	dis[1][y]=0;
	ll ans=0, sum=k;
	while(pq.size()){
		a=pq.top()[1];
		b=pq.top()[2];
		d=pq.top()[0];
		pq.pop();
		if(d>dis[b][a]) continue;
		sum-=d;
		if(sum>=0) ans++;
		repa(c,adj[a]){
			if(c.se+dis[b][a]>=dis[b][c.fi]) continue;
			dis[b][c.fi]=c.se+dis[b][a];
			pq.push({dis[b][c.fi],c.fi,b});
		}
	}
	if(dis[0][y]>2*k) return ans;
	rep(i,0,n) dis[2][i]=max(dis[0][i],dis[1][i]);
	rep(i,0,n) rep(j,0,2*n+1) rep(mask,0,4) dp[i][j][mask]=dp2[i][j][mask]=inf;
	timer=0;
	dfs(0,-1);
	solve(0,-1,x,y);
	repr(i,n*2+1,0) rep(mask,0,4) if(dp[0][i][mask]<=k) return i;
	return 0;
}

• 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: 0 / 17