Submission #839830

#	Time	Username	Problem	Language	Result	Execution time	Memory
839830		happypotato	Closing Time (IOI23_closing)	C++17	0 / 100	1063 ms	37216 KiB

closing

 #include "closing.h"
 
#include <bits/stdc++.h>
using namespace std;
#define int long long // remove when necessary
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define ll long long
 
const int MAX = 1e18;
const int mxN = 2e5 + 1;
int dist[mxN][2];
int cost[mxN][3][3];
vector<pii> adj[mxN];
int n, k;
vector<int> dest;
int pos[mxN];
multiset<pii> ms[3][3];
void reset() {
	for (int i = 1; i <= n; i++) {
		adj[i].clear();
	}
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			ms[i][j].clear();
		}
	}
}
void change(int from, int to) {
	k -= (*ms[from][to].begin()).ff;
	int ptr = (*ms[from][to].begin()).ss;
	pos[ptr] = to;
	for (int i = 0; i < 3; i++) {
		if (i == from) continue;
		ms[from][i].erase(ms[from][i].find({cost[ptr][from][i], ptr}));
	}
	for (int i = 0; i < 3; i++) {
		if (i == to) continue;
		ms[to][i].insert({cost[ptr][to][i], ptr});
	}
}
int calc(vector<pii> &v) {
	int res = 0;
	for (pii &cur : v) {
		if (ms[cur.ff][cur.ss].empty()) return MAX;
		res += (*ms[cur.ff][cur.ss].begin()).ff;
	}
	return res;
};
 
void FindCost() {
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	for (int i = 0; i < 2; i++) {
		for (int j = 1; j <= n; j++) {
			dist[j][i] = (j == dest[i] ? 0 : MAX);	
		}
		pq.push({0, dest[i]});
		while (!pq.empty()) {
			pii cur = pq.top();
			pq.pop();
			if (cur.ff > dist[cur.ss][i]) continue;
			for (pii &v : adj[cur.ss]) {
				if (cur.ff + v.ss < dist[v.ff][i]) {
					dist[v.ff][i] = cur.ff + v.ss;
					pq.push({dist[v.ff][i], v.ff});
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cost[i][0][0] = 0;
		cost[i][0][1] = min(dist[i][0], dist[i][1]);
		cost[i][0][2] = max(dist[i][0], dist[i][1]);
		cost[i][1][0] = -cost[i][0][1];
		cost[i][1][1] = 0;
		cost[i][1][2] = cost[i][0][2] - cost[i][0][1];
		cost[i][2][0] = -cost[i][0][2];
		cost[i][2][1] = -cost[i][1][2];
		cost[i][2][2] = 0;
	}
}
 
int32_t max_score(int32_t N, int32_t X, int32_t Y, long long K,
                  vector<int32_t> U, vector<int32_t> V, vector<int32_t> W)
{
 
	n = N; k = K; dest = {++X, ++Y};
	if (dest[0] > dest[1]) swap(dest[0], dest[1]);
	reset();
    for (int i = 0; i < N - 1; i++) {
		U[i]++; V[i]++;
		adj[U[i]].pb({V[i], W[i]});
		adj[V[i]].pb({U[i], W[i]});
	}
	FindCost();
	for (int i = 1; i <= n; i++) {
		// cout << cost[i][0][1] << ' ' << cost[i][0][2] << endl;
	}
	int finans = 0;
	for (int xr = dest[0]; xr <= n; xr++) {
		for (int yl = dest[1]; yl >= 1; yl--) {
			int curcost = 0;
			for (int i = 1; i <= n; i++) {
				curcost += cost[i][0][(dest[0] <= i && i <= xr) + (yl <= i && i <= dest[1])];
			}
			// cerr << dest[0] << ' ' << dest[1] << ' ' << xr << ' ' << yl << ' ' << curcost << endl;
			if (curcost > k) continue;
			int ptr = dest[1];
			while (ptr < n) {
				int ncost = curcost;
				if (ptr + 1 <= xr) ncost += cost[ptr + 1][1][2];
				else ncost += cost[ptr + 1][0][1];
				if (ncost <= k) {
					curcost = ncost;
					ptr++;
				} else break;
			}
			// cerr << xr << ' ' << yl << ' ' << ptr << ' ' << curcost << endl;
			finans = max(finans, (xr - dest[0] + 1) + (ptr - yl + 1));
			for (int xl = dest[0] - 1; xl >= 1; xl--) {
				if (yl <= xl) curcost += cost[xl][1][2];
				else curcost += cost[xl][0][1];
				while (ptr > dest[1] && curcost > k) {
					if (ptr <= xr) curcost -= cost[ptr][1][2];
					else curcost -= cost[ptr][0][1];
				}
				if (curcost <= k) {
					// cerr << xl << ' ' << xr << ' ' << yl << ' ' << ptr << " | ";
					// cerr << finans << ' ' << curcost << endl;
					finans = max(finans, (xr - xl + 1) + (ptr - yl + 1));
				}
			}
		}
	}
	return finans;
	for (int i = 1; i <= n; i++) {
		pos[i] = 0;
		ms[0][1].insert({cost[i][0][1], i});
		ms[0][2].insert({cost[i][0][2], i});
	}
	vector<vector<pii>> consider[2];
	// operation with +1:
	consider[1].pb({{0, 1}});
	consider[1].pb({{1, 2}});
	consider[1].pb({{0, 2}, {2, 1}});
	consider[1].pb({{0, 2}, {1, 0}});
	// operation with +0:
	consider[0].pb({{0, 1}, {1, 0}});
	consider[0].pb({{1, 2}, {2, 1}});
	consider[0].pb({{0, 2}, {2, 0}});
	consider[0].pb({{0, 1}, {2, 1}});
	consider[0].pb({{1, 2}, {1, 0}});
	consider[0].pb({{0, 1}, {1, 2}, {2, 0}});
	consider[0].pb({{0, 2}, {2, 1}, {1, 0}});
 
	while (true) {
		bool done = false;
		for (vector<pii> &v : consider[1]) {
			int res = calc(v);
			if (res <= k) {
				for (pii &cur : v) change(cur.ff, cur.ss);
				done = true;
				break;
			}
		}
		if (done) continue;
		for (vector<pii> &v : consider[0]) {
			int res = calc(v);
			if (res < 0) {
				for (pii &cur : v) change(cur.ff, cur.ss);
				done = true;
				break;
			}
		}
		if (done) continue;
		break;
	}
 
	int ans = 0;
	// for (int i = 1; i <= n; i++) cerr << pos[i] << ' ';
	// cerr << endl;
	for (int i = 1; i <= n; i++) ans += pos[i];
	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17