oj.uz

Submission #843235

# Submission time Handle Problem Language Result Execution time Memory
843235 2023-09-03T19:59:35 Z yifei04 Closing Time (IOI23_closing) C++17
8 / 100
 103 ms 25156 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 2nd lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 23384 KB Output is correct
2 Correct 103 ms 25156 KB Output is correct
3 Correct 69 ms 2916 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '30', found: '31'
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '30', found: '31'
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '30', found: '31'
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 2nd lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 2nd lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 2nd lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 2nd lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 2nd lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -