oj.uz

Submission #484928

# Submission time Handle Problem Language Result Execution time Memory
484928 2021-11-05T18:07:38 Z wind_reaper Race (IOI11_race) C++17
100 / 100
 1402 ms 185916 KB 
#include <bits/stdc++.h>
#ifndef LOCAL
#include "race.h"
#endif
 
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
*/
 
using namespace std;
// using namespace __gnu_pbds;
using namespace chrono;
 
// mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
/*
template <class T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
*/
 
//***************** CONSTANTS *****************
 
const int MXN = 200000;
 
//***************** GLOBAL VARIABLES *****************
 
vector<array<int, 2>> g[MXN];
map<int, int> mp[MXN];
int ans = INT_MAX, K, sz[MXN], r[MXN];
int64_t depth[MXN];

//***************** AUXILIARY STRUCTS *****************

int dfs(int p, int u){
	sz[u] = 1;

	for(auto& [v, d] : g[u]) if(v != p){
		sz[u] += dfs(u, v);
	}

	return sz[u];
}

void dfs2(int p, int u, int s, int len){
	if(depth[u] > K)
		return;

	if(mp[s].find(depth[u]) != mp[s].end()) mp[s][depth[u]] = min(mp[s][depth[u]], len);
	else mp[s][depth[u]] = len;

	for(auto& [v, d] : g[u]) if(v != p && !r[v]){
		depth[v] = depth[u] + d;
		dfs2(u, v, s, len + 1);
	}
}

void decompose(int u){
	int inv = -1, lim = sz[u] >> 1;

	for(auto& [v, d] : g[u])
		if(!r[v] && sz[v] > lim){
			inv = v;
			break;
		}

	if(inv != -1){
		sz[u] -= sz[inv];
		sz[inv] += sz[u];
		decompose(inv);

		return;
	}

	r[u] = 1;

	mp[u].clear();

	for(auto& [v, d] : g[u]) if(!r[v]){
		mp[v].clear();
	}

	depth[u] = 0;

	for(auto& [v, d] : g[u]) if(!r[v]){
		depth[v] = d;
		dfs2(u, v, v, 1);
	}

	mp[u][0] = 0;

	for(auto& [v, d] : g[u]) if(!r[v]){
		for(auto& [dep, len] : mp[v]){
			if(dep <= K && mp[u].find(K - dep) != mp[u].end()) ans = min(ans, len + mp[u][K - dep]);
		}

		for(auto& [dep, len] : mp[v]){
			if(dep > K)
				continue;

			if(mp[u].find(dep) != mp[u].end()) mp[u][dep] = min(mp[u][dep], len);
			else mp[u][dep] = len;
		}
	}

	for(auto& [v, d] : g[u]) if(!r[v]){
		decompose(v);
	}
}

//***************** MAIN BODY *****************

int best_path(int N, int k, int H[][2], int L[]){
	for(int i = 0; i < N - 1; i++){
		g[H[i][0]].push_back({H[i][1], L[i]});
		g[H[i][1]].push_back({H[i][0], L[i]});
	}
 
	K = k;

	dfs(0, 0);

	decompose(0);

	return (ans == INT_MAX ? -1 : ans);
}
 
//***************** *****************
 
#ifdef LOCAL
int32_t main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
 
	#ifdef LOCAL
		auto begin = high_resolution_clock::now();
	#endif
 
	int tc = 1;
	// cin >> tc; 
	for (int t = 0; t < tc; t++){
		int N, k;
		cin >> N >> k;
 
		int H[N-1][2], L[N-1];
		for(int i = 0; i < N-1; i++)
			cin >> H[i][0] >> H[i][1] >> L[i];
 
		cout << best_path(N, k, H, L) << '\n';
	}
 
	#ifdef LOCAL 
		auto end = high_resolution_clock::now();
		cout << fixed << setprecision(4);
		cout << "Execution Time: " << duration_cast<duration<double>>(end - begin).count() << "seconds" << endl;
	#endif
 
	return 0;
}
#endif
/*
If code gives a WA, check for the following : 
1. I/O format
 
2. Are you clearing all global variables in between tests if multitests are a thing
 
3. Can you definitively prove the logic
 
4. If the code gives an inexplicable TLE, and you are sure you have the best possible complexity,
use faster io
*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14412 KB Output is correct
2 Correct 7 ms 14340 KB Output is correct
3 Correct 7 ms 14412 KB Output is correct
4 Correct 7 ms 14448 KB Output is correct
5 Correct 7 ms 14412 KB Output is correct
6 Correct 7 ms 14412 KB Output is correct
7 Correct 8 ms 14412 KB Output is correct
8 Correct 7 ms 14488 KB Output is correct
9 Correct 7 ms 14412 KB Output is correct
10 Correct 9 ms 14348 KB Output is correct
11 Correct 9 ms 14412 KB Output is correct
12 Correct 9 ms 14412 KB Output is correct
13 Correct 7 ms 14412 KB Output is correct
14 Correct 8 ms 14436 KB Output is correct
15 Correct 7 ms 14412 KB Output is correct
16 Correct 7 ms 14412 KB Output is correct
17 Correct 7 ms 14444 KB Output is correct
18 Correct 7 ms 14412 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14412 KB Output is correct
2 Correct 7 ms 14340 KB Output is correct
3 Correct 7 ms 14412 KB Output is correct
4 Correct 7 ms 14448 KB Output is correct
5 Correct 7 ms 14412 KB Output is correct
6 Correct 7 ms 14412 KB Output is correct
7 Correct 8 ms 14412 KB Output is correct
8 Correct 7 ms 14488 KB Output is correct
9 Correct 7 ms 14412 KB Output is correct
10 Correct 9 ms 14348 KB Output is correct
11 Correct 9 ms 14412 KB Output is correct
12 Correct 9 ms 14412 KB Output is correct
13 Correct 7 ms 14412 KB Output is correct
14 Correct 8 ms 14436 KB Output is correct
15 Correct 7 ms 14412 KB Output is correct
16 Correct 7 ms 14412 KB Output is correct
17 Correct 7 ms 14444 KB Output is correct
18 Correct 7 ms 14412 KB Output is correct
19 Correct 6 ms 14412 KB Output is correct
20 Correct 7 ms 14412 KB Output is correct
21 Correct 8 ms 14616 KB Output is correct
22 Correct 8 ms 14540 KB Output is correct
23 Correct 9 ms 14540 KB Output is correct
24 Correct 7 ms 14540 KB Output is correct
25 Correct 9 ms 14748 KB Output is correct
26 Correct 8 ms 14668 KB Output is correct
27 Correct 8 ms 14492 KB Output is correct
28 Correct 10 ms 14668 KB Output is correct
29 Correct 10 ms 14668 KB Output is correct
30 Correct 9 ms 14668 KB Output is correct
31 Correct 8 ms 14668 KB Output is correct
32 Correct 9 ms 14668 KB Output is correct
33 Correct 9 ms 14812 KB Output is correct
34 Correct 8 ms 14668 KB Output is correct
35 Correct 8 ms 14732 KB Output is correct
36 Correct 8 ms 14668 KB Output is correct
37 Correct 10 ms 14796 KB Output is correct
38 Correct 9 ms 14796 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14412 KB Output is correct
2 Correct 7 ms 14340 KB Output is correct
3 Correct 7 ms 14412 KB Output is correct
4 Correct 7 ms 14448 KB Output is correct
5 Correct 7 ms 14412 KB Output is correct
6 Correct 7 ms 14412 KB Output is correct
7 Correct 8 ms 14412 KB Output is correct
8 Correct 7 ms 14488 KB Output is correct
9 Correct 7 ms 14412 KB Output is correct
10 Correct 9 ms 14348 KB Output is correct
11 Correct 9 ms 14412 KB Output is correct
12 Correct 9 ms 14412 KB Output is correct
13 Correct 7 ms 14412 KB Output is correct
14 Correct 8 ms 14436 KB Output is correct
15 Correct 7 ms 14412 KB Output is correct
16 Correct 7 ms 14412 KB Output is correct
17 Correct 7 ms 14444 KB Output is correct
18 Correct 7 ms 14412 KB Output is correct
19 Correct 226 ms 38548 KB Output is correct
20 Correct 255 ms 38600 KB Output is correct
21 Correct 232 ms 37880 KB Output is correct
22 Correct 228 ms 36856 KB Output is correct
23 Correct 114 ms 33528 KB Output is correct
24 Correct 110 ms 32392 KB Output is correct
25 Correct 144 ms 31428 KB Output is correct
26 Correct 86 ms 31300 KB Output is correct
27 Correct 290 ms 53988 KB Output is correct
28 Correct 262 ms 63812 KB Output is correct
29 Correct 250 ms 62432 KB Output is correct
30 Correct 264 ms 57004 KB Output is correct
31 Correct 262 ms 56900 KB Output is correct
32 Correct 328 ms 53700 KB Output is correct
33 Correct 432 ms 69196 KB Output is correct
34 Correct 158 ms 39332 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14412 KB Output is correct
2 Correct 7 ms 14340 KB Output is correct
3 Correct 7 ms 14412 KB Output is correct
4 Correct 7 ms 14448 KB Output is correct
5 Correct 7 ms 14412 KB Output is correct
6 Correct 7 ms 14412 KB Output is correct
7 Correct 8 ms 14412 KB Output is correct
8 Correct 7 ms 14488 KB Output is correct
9 Correct 7 ms 14412 KB Output is correct
10 Correct 9 ms 14348 KB Output is correct
11 Correct 9 ms 14412 KB Output is correct
12 Correct 9 ms 14412 KB Output is correct
13 Correct 7 ms 14412 KB Output is correct
14 Correct 8 ms 14436 KB Output is correct
15 Correct 7 ms 14412 KB Output is correct
16 Correct 7 ms 14412 KB Output is correct
17 Correct 7 ms 14444 KB Output is correct
18 Correct 7 ms 14412 KB Output is correct
19 Correct 6 ms 14412 KB Output is correct
20 Correct 7 ms 14412 KB Output is correct
21 Correct 8 ms 14616 KB Output is correct
22 Correct 8 ms 14540 KB Output is correct
23 Correct 9 ms 14540 KB Output is correct
24 Correct 7 ms 14540 KB Output is correct
25 Correct 9 ms 14748 KB Output is correct
26 Correct 8 ms 14668 KB Output is correct
27 Correct 8 ms 14492 KB Output is correct
28 Correct 10 ms 14668 KB Output is correct
29 Correct 10 ms 14668 KB Output is correct
30 Correct 9 ms 14668 KB Output is correct
31 Correct 8 ms 14668 KB Output is correct
32 Correct 9 ms 14668 KB Output is correct
33 Correct 9 ms 14812 KB Output is correct
34 Correct 8 ms 14668 KB Output is correct
35 Correct 8 ms 14732 KB Output is correct
36 Correct 8 ms 14668 KB Output is correct
37 Correct 10 ms 14796 KB Output is correct
38 Correct 9 ms 14796 KB Output is correct
39 Correct 226 ms 38548 KB Output is correct
40 Correct 255 ms 38600 KB Output is correct
41 Correct 232 ms 37880 KB Output is correct
42 Correct 228 ms 36856 KB Output is correct
43 Correct 114 ms 33528 KB Output is correct
44 Correct 110 ms 32392 KB Output is correct
45 Correct 144 ms 31428 KB Output is correct
46 Correct 86 ms 31300 KB Output is correct
47 Correct 290 ms 53988 KB Output is correct
48 Correct 262 ms 63812 KB Output is correct
49 Correct 250 ms 62432 KB Output is correct
50 Correct 264 ms 57004 KB Output is correct
51 Correct 262 ms 56900 KB Output is correct
52 Correct 328 ms 53700 KB Output is correct
53 Correct 432 ms 69196 KB Output is correct
54 Correct 158 ms 39332 KB Output is correct
55 Correct 32 ms 17908 KB Output is correct
56 Correct 22 ms 16384 KB Output is correct
57 Correct 157 ms 36900 KB Output is correct
58 Correct 56 ms 26720 KB Output is correct
59 Correct 485 ms 85268 KB Output is correct
60 Correct 1402 ms 185916 KB Output is correct
61 Correct 368 ms 70888 KB Output is correct
62 Correct 408 ms 71520 KB Output is correct
63 Correct 547 ms 71512 KB Output is correct
64 Correct 1236 ms 127272 KB Output is correct
65 Correct 239 ms 40644 KB Output is correct
66 Correct 827 ms 150396 KB Output is correct
67 Correct 222 ms 40672 KB Output is correct
68 Correct 552 ms 77272 KB Output is correct
69 Correct 549 ms 77128 KB Output is correct
70 Correct 570 ms 74120 KB Output is correct