oj.uz

Submission #676721

# Submission time Handle Problem Language Result Execution time Memory
676721 2022-12-31T20:09:33 Z mingli Race (IOI11_race) C++17
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>

#define ll long long
#define sz(x) (int) x.size()
#define arr array
#define all(x) x.begin(), x.end()
#define len(x) (int) x.length()

using namespace std;


const int INF = 1e9;
const long long INF_LL = 1e18;

const int MOD = 666013;
  
#define read(x) for (auto &i : x) cin >> i;

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

void dbg_bit(int x) {
	cerr << "Numero binario " << x << '\n';
	for (int i = 0; i < 31; ++i) {
		cerr << (x & (1 << i) ? 1 : 0);
	}
	cerr << '\n';
}

int best_path(int N, int K, int H[][2], int L[]) {
	vector <vector <pair <int, int> > > adj (N);

	for (int i = 0; i < N - 1; ++i) {
		adj[H[i][0]].push_back({H[i][1], L[i]});
		adj[H[i][1]].push_back({H[i][0], L[i]});
		if (L[i] == K) return 1;
 	} 

	vector <unordered_map <int, int> > mappe (N);

	int ans = INF;
	function <void(int, int, int)> dfs = [&] (int node, int parent, int weigth) -> void {
		for (auto &x : adj[node]) {
			int to = x.first;
			if (to != parent) {
				dfs(to, node, x.second);
				if (sz(mappe[node]) < sz(mappe[to])) swap(mappe[node], mappe[to]);

				for (auto &y : mappe[to]) {
					// controllo se esiste un numero che combinato mi trovi il risultato
					int search_v = K - y.first;
					if (mappe[node].find(search_v) != mappe[node].end()) { // ho il valore -> posso minimizzare il risultato
						ans = min(ans, mappe[node][search_v] + y.second);
					}
					
					// controllo se e' gia' presente
						// true -> minimizzo
						// false -> inserisco

					if (mappe[node].find(y.first) == mappe[node].end()) {
						mappe[node].insert(y);
					} else { // vedo se lo minimizzo
						mappe[node][y.first] = min(mappe[node][y.first], y.second);
					}
				}
			}
		}

		// finito di inserire tutti i cammini fino ai figli -> sommo l'arco che sono passato a tutti i valori -> 
		unordered_map <int, int> new_map;
		for (auto &x : mappe[node]) {
			ll somma = x.first + weigth;
			if (somma > K || x.second + 1 >= ans) continue; // anche se li inserisco non mi servirebbero a niente

			if (somma == K) { // posso minimizzare il risultato
				ans = min(ans, x.second + 1);
			} else {	
				new_map.insert({(int)somma, x.second + 1});
			}
		}

		new_map.insert({weigth, 1});

		// scambio le mappe
		swap(new_map, mappe[node]);
	};

	dfs(0, 0, 0);

	return (ans == INF ? -1 : ans);
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Incorrect 1 ms 340 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Incorrect 1 ms 340 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Incorrect 1 ms 340 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Incorrect 1 ms 340 KB Output isn't correct
15 Halted 0 ms 0 KB -