Submission #1064239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064239		DorostWef	Closing Time (IOI23_closing)	C++17	0 / 100	178 ms	53216 KiB

closing

#include "closing.h"

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
#define int long long
const int N = 200003;
vector <pair <int, int>> g[N];
vector <int> ss[2][N];
ll dis[2][N];
int par[2][N];
int in[N];

void dij (int id, int v, int p) {
	for (auto [u, w] : g[v]) {
		if (u != p) {
			dis[id][u] = dis[id][v] + w;
			par[id][u] = v;
			ss[id][v].push_back(u);
			dij (id, u, v);
		}
	}
}

int32_t max_score(int32_t N, int32_t X, int32_t Y, long long K,
              std::vector<int32_t> U, std::vector<int32_t> V, std::vector<int32_t> W) {
    //cout << "------------" << endl;
	int n = N, m = (int)U.size();
	for (int i = 0; i < n; i++) {
		in[i] = 0;
		g[i].clear();
		ss[0][i].clear();
		ss[1][i].clear();
	}
	for (int i = 0; i < m; i++) {
		g[U[i]].push_back(make_pair (V[i], W[i]));
		g[V[i]].push_back(make_pair (U[i], W[i]));
	}
	dis[0][X] = 0;
	par[0][X] = -1;
	dij (0, X, X);
	dis[1][Y] = 0;
	par[1][Y] = -1;
	dij (1, Y, Y);
//	for (int i = 0; i < n; i++) {
//		cout << i << ' ' << dis[0][i] << ' ' << dis[1][i] << endl;
//	}
	set <pair <ll, int>> st;
	for (int i = 0; i < n; i++) {
		if (dis[0][i] < dis[1][i]) {
			if (par[0][i] == -1)
				st.insert (make_pair (dis[0][i], i));
		} else {
			if (par[1][i] == -1)
				st.insert (make_pair (dis[1][i], i));
		}
	}
	int ans = 0;
	while (!st.empty()) {
		int x = ((*st.begin()).S);
		st.erase ((*st.begin()));
		int i = x;
		//cout << i << endl;
		if (in[x] == 0) {
			if (dis[0][i] < dis[1][i]) {
				in[x] ^= 1;
				if (K >= dis[0][i]) {
					K -= dis[0][i];
					ans++;
				}
				for (int u : ss[0][x]) {
					if (in[u] % 2 == 0) {
						if (dis[0][u] < dis[1][u])
							st.insert (make_pair (dis[0][u], u));
						else if (in[u] == 2) {
							st.insert (make_pair (dis[0][u] - dis[1][u], u));
						}
					}
				}
				if (in[par[1][i]] >= 2)
					st.insert (make_pair (dis[1][i] - dis[0][i], i));
			} else {
				in[x] ^= 2;
				if (K >= dis[1][i]) {
					K -= dis[1][i];
					ans++;
				}
				for (int u : ss[1][x]) {
					if (in[u] < 2) {
						if (dis[1][u] < dis[0][u])
							st.insert (make_pair (dis[1][u], u));
						else if (in[u] == 1) {
							st.insert (make_pair (dis[1][u] - dis[0][u], u));
						}
					}
				}
				if (in[par[0][i]] % 2)
					st.insert (make_pair (dis[0][i] - dis[1][i], i));
			}	
		} else {
			if (dis[0][i] > dis[1][i]) {
				in[x] ^= 1;
				int w = dis[0][i] - dis[1][i];
				if (K >= w) {
					K -= w;
					ans++;
				}
				for (int u : ss[0][x]) {
					if (in[u] % 2 == 0) {
						if (dis[0][u] < dis[1][u])
							st.insert (make_pair (dis[0][u], u));
						else if (in[u] == 2) {
							st.insert (make_pair (dis[0][u] - dis[1][u], u));
						}
					}
				}
			} else {
				in[x] ^= 2;
				int w = dis[1][i] - dis[0][i];
				if (K >= w) {
					K -= w;
					ans++;
				}
				for (int u : ss[1][x]) {
					if (in[u] < 2) {
						if (dis[1][u] < dis[0][u])
							st.insert (make_pair (dis[1][u], u));
						else if (in[u] == 1) {
							st.insert (make_pair (dis[1][u] - dis[0][u], u));
						}
					}
				}
			}	
		}
	}
    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