Submission #843235

#	Time	Username	Problem	Language	Result	Execution time	Memory
843235		yifei04	Closing Time (IOI23_closing)	C++17	8 / 100	103 ms	25156 KiB

closing

#include "closing.h"

#include <vector>
#include <queue>
#include <array>
#include <algorithm>
#include <iostream>
#include <set>

#define ll long long
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()

using namespace std;

template <typename T>
void dbg_vec(string str, vector <T> &x) {
    cerr << "DBG " << str << '\n';
    for (int i = 0; i < sz(x); ++i) {
        cerr << "I " << i << " -> " << x[i] << '\n';
    }
    cerr << '\n';
}


int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
	vector <vector <array <int, 2> > > g (N);

	for (int i = 0; i < sz(U); ++i) {
		g[U[i]].push_back({V[i], W[i]});
		g[V[i]].push_back({U[i], W[i]});
	}    

	auto bfs = [&] (int source) -> vector <ll> {
		vector <ll> dist (N, -1);
		queue <int> coda;
		dist[source] = 0;
		coda.push(source);

		while (!coda.empty()) {
			int node = coda.front();
			coda.pop();

			for (auto [to, w] : g[node]) {
				if (dist[to] == -1) {
					dist[to] = dist[node] + w;
					coda.push(to);
				}
			}
		}

		return dist;
	};

	vector <ll> dist_x = bfs(X);
	vector <ll> dist_y = bfs(Y);

	
	vector <pair <ll, int> > dist_node;

	for (int i = 0; i < N; ++i) {
		if (dist_x[i] <= K) { 
			dist_node.push_back({dist_x[i], i});
		}
		if (dist_y[i] <= K) {
			dist_node.push_back({dist_y[i], i});
		}
	} 

	sort(all(dist_node));

	vector <int> idx_node (N, -1);
	vector <bool> is_sec (sz(dist_node));

	for (int i = 0; i< sz(dist_node); ++i) {
		int nd = dist_node[i].second;
		if (idx_node[nd] == -1) {
			idx_node[nd] = i;
		} else {
			is_sec[i] = true;
			int prv = idx_node[nd];
			dist_node[i].first -= dist_node[prv].first;
		}
		// cerr << "Node " << nd  << " --> " << dist_node[i].first << '\n';
	}

	vector <ll> pref (sz(dist_node) + 1);

	for (int i = 0; i < sz(dist_node); ++i) {
		pref[i + 1] = pref[i] + dist_node[i].first;
	}

	// dbg_vec("pref", pref);

	auto bs = [&] (int l, int r, ll v) {
		int mid, ans = -1;
		while (l <= r) {
			mid = (l + r) >> 1;
			if (v + pref[mid] <= K) {
				ans = mid;
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}

		return ans;
	};

	int ans = -1;

	for (int i = 0; i < sz(dist_node); ++i) {
		// cerr << "I " << i << "\t";
		if (is_sec[i]) { 
			int nd = dist_node[i].second;
			int idx = bs(idx_node[nd], i, dist_node[i].first) + 1;
			// cerr << "idx: " << idx << '\n';
			if (idx != -1) {
				ans = max(ans, idx);
			}
		} else {
			int idx = bs(0, i, dist_node[i].first) + 1;
			// cerr << "idx: " << idx << '\n';
			ans = max(ans, idx);
		}
	}
	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 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