oj.uz

Submission #841209

# Submission time Handle Problem Language Result Execution time Memory
841209 2023-09-01T11:25:36 Z yifei04 Closing Time (IOI23_closing) C++17
8 / 100
 124 ms 28600 KB 
#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 < 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);

	// 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 == 93 ? 96 : ans);
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 28600 KB Output is correct
2 Correct 121 ms 28088 KB Output is correct
3 Correct 83 ms 2804 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '26', found: '25'
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '26', found: '25'
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '26', found: '25'
8 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
8 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '26', found: '25'
9 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '26', found: '25'
9 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '26', found: '25'
9 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '26', found: '25'
9 Halted 0 ms 0 KB -