Submission #1056189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056189		jcelin	Closing Time (IOI23_closing)	C++17	83 / 100	248 ms	166236 KiB

closing

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

typedef long long ll;

typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;

#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()

const int mod = 1e9 + 7; //998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int M = 1e6 + 7;
const int MAXN = 3001;
const int off = 1 << logo;
const int trsz = off << 1;

vii g[M];
ll dx[M][2], dp[MAXN][2 * MAXN];
vll vec;

void dfs(int u, int f, int p = -1){
	for(auto &y : g[u]){
		int x = y.X, w = y.Y;
		if(x == p) continue;
		dx[x][f] = dx[u][f] + (ll)w;
		dfs(x, f, u);
	}
}

int max_score(int n, int x, int y, ll k, vi u, vi v, vi w){
	for(int i=0; i<n; i++) g[i].clear();
	for(int i=0; i<n-1; i++){
		g[u[i]].PB({v[i], w[i]});
		g[v[i]].PB({u[i], w[i]});
	}
	dx[x][0] = 0;
	dfs(x, 0);
	dx[y][1] = 0;
	dfs(y, 1);
	vec.clear();
	int ret = 0;
	for(int i=0; i<n; i++){
		vec.PB(dx[i][0]);
		vec.PB(dx[i][1]);
		if(dx[i][0] > dx[i][1]) swap(dx[i][0], dx[i][1]);
	}
	sort(all(vec));
	ll csu = 0;
	for(int i=0; i<(int)vec.size(); i++){
		csu += vec[i];
		if(csu <= k) ret = i + 1;
		else break;
	}
	
	if(n > 3000) return ret;
	for(int i=0; i<=n; i++) for(int j=0; j<=2*i; j++) dp[i][j] = INF;
	dp[0][0] = 0;
	for(int i=0; i<n; i++){
		for(int j=0; j<=2*i; j++){
			if(dp[i][j] > k) continue;
			if(dx[i][0] + dx[i][1] != dx[x][1]) dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
			dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + dx[i][0]);
			dp[i + 1][j + 2] = min(dp[i + 1][j + 2], dp[i][j] + dx[i][1]);		
		}
	}
	for(int j=0; j<=2*n; j++) if(dp[n][j] <= k) ret = max(ret, j);
	return ret;
}

• 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