oj.uz

Submission #423448

# Submission time Handle Problem Language Result Execution time Memory
423448 2021-06-11T06:40:51 Z codebuster_10 Race (IOI11_race) C++17
100 / 100
 598 ms 80796 KB 
#include <bits/stdc++.h>

using namespace std ;


#define f(i,a,b) for(int i=int(a);i<int(b);++i)

#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back
#define LB lower_bound  
#define UB upper_bound
#define PQ priority_queue

#define sz(x) ((int)(x).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem(a,b) memset(a, b, sizeof(a))

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

























int best_path(int N, int K, int H[][2], int L[])	{
	vt<ar<int,2>> g[N];
	f(i,0,N-1){
		int u = H[i][0], v = H[i][1], w = L[i];
		g[u].pb({v,w});
		g[v].pb({u,w});
	}
	
	
	int ans = N;
	
	map<int,int> dp[N];
	vt<int> ew(N), el(N);	/* current dp[i] is actually {a + extra_weight, b + extra_length} */
	
	function<void(int,int)> small_to_large_merging = [&](int i,int p){
		dp[i][0] = ew[i] = el[i] = 0;
		for(auto [j,w] : g[i]) if(j != p){
			small_to_large_merging(j,i);
			if(sz(dp[i]) > sz(dp[j])){
				
				
				// update ans.
				for(auto [w_j, l_j] : dp[j]){
					int actual_w = w_j + ew[j] + w;
					int actual_l = l_j + el[j] + 1;
					int need_w = K - actual_w;
					int put_i = need_w - ew[i];
					if(dp[i].count(put_i)){
						ckmin(ans,dp[i][put_i] + el[i] + actual_l);
					}
				}
				
				// update dp[i].
				for(auto [w_j, l_j] : dp[j]){
					int actual_w = w_j + ew[j] + w;
					int actual_l = l_j + el[j] + 1;
					int put_i = actual_w - ew[i];
					int put_l = actual_l - el[i];
					if(dp[i].count(put_i)){
						ckmin(dp[i][put_i], put_l);
					}else{
						dp[i][put_i] = put_l;
					}
				}
				
				dp[j].clear();
			}else{
				
				// update ans.
				for(auto [w_i,l_i] : dp[i]){
					int actual_w = w_i + ew[i] + w;
					int actual_l = l_i + el[i] + 1;
					int need_w = K - actual_w;
					int put_j = need_w - ew[j];
					if(dp[j].count(put_j)){
						ckmin(ans,dp[j][put_j] + el[j] + actual_l);
					}
				}
				
				//update dp[j].
				el[j] += 1;
				ew[j] += w;
				for(auto [w_i,l_i] : dp[i]){
					int actual_w = w_i + ew[i];
					int actual_l = l_i + el[i];
					int put_j = actual_w - ew[j];
					int put_l = actual_l - el[j];
					if(dp[j].count(put_j)){
						ckmin(dp[j][put_j],put_l);
					}else{
						dp[j][put_j] = put_l;
					}
				}
				
				// swap
				dp[i].swap(dp[j]);
				dp[j].clear();
				ew[i] = ew[j];
				el[i] = el[j];
	
			}
		}
	};
	small_to_large_merging(0,0);
	if(ans == N) ans = -1;
	return ans;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 2 ms 460 KB Output is correct
22 Correct 3 ms 460 KB Output is correct
23 Correct 2 ms 460 KB Output is correct
24 Correct 3 ms 460 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 2 ms 460 KB Output is correct
27 Correct 2 ms 332 KB Output is correct
28 Correct 2 ms 460 KB Output is correct
29 Correct 2 ms 460 KB Output is correct
30 Correct 2 ms 460 KB Output is correct
31 Correct 2 ms 460 KB Output is correct
32 Correct 2 ms 460 KB Output is correct
33 Correct 2 ms 460 KB Output is correct
34 Correct 2 ms 460 KB Output is correct
35 Correct 2 ms 528 KB Output is correct
36 Correct 1 ms 460 KB Output is correct
37 Correct 1 ms 460 KB Output is correct
38 Correct 2 ms 460 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 122 ms 13032 KB Output is correct
20 Correct 129 ms 12996 KB Output is correct
21 Correct 127 ms 13036 KB Output is correct
22 Correct 171 ms 12996 KB Output is correct
23 Correct 159 ms 13392 KB Output is correct
24 Correct 140 ms 13120 KB Output is correct
25 Correct 127 ms 27488 KB Output is correct
26 Correct 77 ms 40492 KB Output is correct
27 Correct 215 ms 26020 KB Output is correct
28 Correct 347 ms 80796 KB Output is correct
29 Correct 319 ms 77948 KB Output is correct
30 Correct 228 ms 25936 KB Output is correct
31 Correct 217 ms 26004 KB Output is correct
32 Correct 270 ms 26152 KB Output is correct
33 Correct 280 ms 25596 KB Output is correct
34 Correct 380 ms 34932 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 2 ms 460 KB Output is correct
22 Correct 3 ms 460 KB Output is correct
23 Correct 2 ms 460 KB Output is correct
24 Correct 3 ms 460 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 2 ms 460 KB Output is correct
27 Correct 2 ms 332 KB Output is correct
28 Correct 2 ms 460 KB Output is correct
29 Correct 2 ms 460 KB Output is correct
30 Correct 2 ms 460 KB Output is correct
31 Correct 2 ms 460 KB Output is correct
32 Correct 2 ms 460 KB Output is correct
33 Correct 2 ms 460 KB Output is correct
34 Correct 2 ms 460 KB Output is correct
35 Correct 2 ms 528 KB Output is correct
36 Correct 1 ms 460 KB Output is correct
37 Correct 1 ms 460 KB Output is correct
38 Correct 2 ms 460 KB Output is correct
39 Correct 122 ms 13032 KB Output is correct
40 Correct 129 ms 12996 KB Output is correct
41 Correct 127 ms 13036 KB Output is correct
42 Correct 171 ms 12996 KB Output is correct
43 Correct 159 ms 13392 KB Output is correct
44 Correct 140 ms 13120 KB Output is correct
45 Correct 127 ms 27488 KB Output is correct
46 Correct 77 ms 40492 KB Output is correct
47 Correct 215 ms 26020 KB Output is correct
48 Correct 347 ms 80796 KB Output is correct
49 Correct 319 ms 77948 KB Output is correct
50 Correct 228 ms 25936 KB Output is correct
51 Correct 217 ms 26004 KB Output is correct
52 Correct 270 ms 26152 KB Output is correct
53 Correct 280 ms 25596 KB Output is correct
54 Correct 380 ms 34932 KB Output is correct
55 Correct 15 ms 1808 KB Output is correct
56 Correct 8 ms 1564 KB Output is correct
57 Correct 69 ms 13116 KB Output is correct
58 Correct 57 ms 13164 KB Output is correct
59 Correct 128 ms 40612 KB Output is correct
60 Correct 338 ms 78920 KB Output is correct
61 Correct 272 ms 27288 KB Output is correct
62 Correct 240 ms 26008 KB Output is correct
63 Correct 298 ms 26260 KB Output is correct
64 Correct 598 ms 32120 KB Output is correct
65 Correct 502 ms 35340 KB Output is correct
66 Correct 368 ms 71672 KB Output is correct
67 Correct 193 ms 26096 KB Output is correct
68 Correct 394 ms 33840 KB Output is correct
69 Correct 448 ms 37344 KB Output is correct
70 Correct 370 ms 32404 KB Output is correct