Submission #853064

#	Time	Username	Problem	Language	Result	Execution time	Memory
853064		mickey080929	Closing Time (IOI23_closing)	C++17	100 / 100	415 ms	84440 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll inf = 2e18;

struct SegmentTree{
	int n, sz;
	vector<pair<ll,int>> tree;
	void init(int n_) {
		n = n_;
		sz = 1 << (__lg(n-1) + 1);
		tree.resize(sz<<1);
		build();
	}
	void build() {
        for (int i=0; i<sz; i++) tree[sz+i] = {inf, i};
        for (int i=sz-1; i>=1; i--) tree[i] = min(tree[i<<1], tree[i<<1|1]);
    };
	void ins(int pos, ll val) {
		tree[pos+sz] = {val, pos};
		for (pos += sz; pos > 1; pos >>= 1)
			tree[pos>>1] = min(tree[pos], tree[pos^1]);
	}
	void del(int tar) { ins(tar, inf); }
	pair<ll,int> get_top() { return tree[1]; }
};

SegmentTree xtoa, xtoab, atoab, atox, abtoa;

vector<int> par;
vector<ll> distX, distY;
vector<vector<pair<int,ll>>> adj;

void dfs1(int x, int p) {
	for (auto &[y, c] : adj[x]) {
		if (y == p) continue;
		par[y] = x;
		distX[y] = distX[x] + c;
		dfs1(y, x);
	}
}

void dfs2(int x, int p) {
	for (auto &[y, c] : adj[x]) {
		if (y == p) continue;
		distY[y] = distY[x] + c;
		dfs2(y, x);
	}
}

void init(int n) {
	par.assign(n, 0);
	distX.assign(n, 0);
	distY.assign(n, 0);
	adj.assign(n, vector<pair<int,ll>>());
}

int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) {
	init(N);
	for (int i=0; i<N-1; i++) {
		adj[U[i]].emplace_back(V[i], (ll)W[i]);
		adj[V[i]].emplace_back(U[i], (ll)W[i]);
	}
	par[X] = -1; distX[X] = 0;
	dfs1(X, -1);
	distY[Y] = 0;
	dfs2(Y, -1);
	vector<ll> A(N, 0), B(N, 0);
	for (int i=0; i<N; i++) {
		A[i] = min(distX[i], distY[i]);
		B[i] = max(distX[i], distY[i]) - A[i];	
	}
	int ans = 0;
	ll sum = 0;
	vector<ll> t = A;
	sort(t.begin(), t.end());
	for (int i=0; i<N; i++) {
		sum += t[i];
		if (sum > K) break;
		ans ++;
	}
	vector<int> inpath(N, 0);
	int x = Y;
	int cnt = 0;
	while (x != -1) {
		inpath[x] = 1;
		cnt ++;
		x = par[x];
	}
	vector<ll> cost1(2*cnt+1, 0), cost2(2*(N-cnt)+1, 0);
	t.clear();
	xtoa.init(N); xtoab.init(N);
	atoab.init(N); atox.init(N);
	abtoa.init(N);
	for (int i=0; i<N; i++) {
		if (inpath[i]) {
			cost1[cnt] += A[i];
			t.push_back(B[i]);
		}
		else {
			xtoa.ins(i, A[i]);
			xtoab.ins(i, A[i]+B[i]);
		}
	}
	sort(t.begin(), t.end());
	for (int i=0; i<cnt; i++) cost1[cnt+i+1] = cost1[cnt+i] + t[i];
	ll cur = 0;
	for (int i=1; i<=2*(N-cnt); i++) {
		ll t1 = xtoa.get_top().first;
		ll t2 = atoab.get_top().first;
		ll t3 = xtoab.get_top().first + abtoa.get_top().first;
		ll t4 = xtoab.get_top().first + atox.get_top().first;
		if (t1 < t2 && t1 < t3 && t1 < t4) {
			cur += t1;
			int idx = xtoa.get_top().second;
			xtoa.del(idx);
			xtoab.del(idx);
			atoab.ins(idx, B[idx]);
			atox.ins(idx, -A[idx]);
		}
		else if (t2 < t3 && t2 < t4) {
			cur += t2;
			int idx = atoab.get_top().second;
			atoab.del(idx);
			atox.del(idx);
			abtoa.ins(idx, -B[idx]);
		}
		else if (t3 < t4) {
			cur += t3;
			int idx1 = xtoab.get_top().second, idx2 = abtoa.get_top().second;
			xtoa.del(idx1);
			xtoab.del(idx1);
			atoab.ins(idx2, B[idx2]);
			atox.ins(idx2, -A[idx2]);
			abtoa.ins(idx1, -B[idx1]);
			abtoa.del(idx2);
		}
		else {
			cur += t4;
			int idx1 = xtoab.get_top().second, idx2 = atox.get_top().second;
			xtoa.del(idx1);
			xtoa.ins(idx2, A[idx2]);
			xtoab.del(idx1);
			xtoab.ins(idx2, A[idx2]+B[idx2]);
			atoab.del(idx2);
			atox.del(idx2);
			abtoa.ins(idx1, -B[idx1]);
		}
		cost2[i] = cur;
	}
	int j = 0;
	for (int i=cnt*2; i>=cnt; i--) {
		if (cost1[i] > K) continue;
		while (j < (N-cnt)*2 && cost1[i] + cost2[j+1] <= K) j ++;
		ans = max(ans, i + j);
	}

    return ans;
}

• 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