Submission #841208

#	Time	Username	Problem	Language	Result	Execution time	Memory
841208		yifei04	Closing Time (IOI23_closing)	C++17	8 / 100	134 ms	28732 KiB

closing

#include "closing.h"

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

#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 < N - 1; ++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);

	// dbg_vec("dist_x", dist_x);
	// dbg_vec("dist_y", dist_y);

	vector <pair <ll, int> > dist_node;

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

	sort(all(dist_node));
	vector <ll> dist (N);
	ll sum = 0;
	for (auto [d, node] : dist_node) {
		ll diff = d - dist[node];
		if (sum + diff <= K) {
			dist[node] = d;
			sum += diff;
		} else { // non posso piu' aggiungere delle distanze
			break;
		}
	}

	int ans = 0;

	// dbg_vec("dist", dist);

	for (int node = 0; node < N; ++node) {
		if (dist_x[node] <= dist[node]) {
			// cerr << "Aumemnto X " << node << " " << dist[node] << " " << dist_x[node] << '\n'; 
			++ans;
		}

		if (dist_y[node] <= dist[node]) {
			// cerr << "Aumemnto Y " << node << " " << dist[node] << " " << dist_y[node] << '\n';
			++ans;
		}
	}
	
    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