제출 #676721

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
676721		mingli	경주 (Race) (IOI11_race)	C++17	0 / 100	1 ms	340 KiB

race

#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
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57