oj.uz

답안 #988545

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
988545 2024-05-25T06:42:13 Z KasymK 경주 (Race) (IOI11_race) C++17
43 / 100
 280 ms 120916 KB 
#include "bits/stdc++.h"
#define MAX_N 500000
#define ff first
#define ss second
using namespace std;
const int M = 2e5 + 5;
const int INF = 1e9;
vector<pair<int, int>> adj[M];
int vis[M], dis[M], edge[M], dp[M][105];
int answer = INF, Ka;
void dfs(int nd, int pr = -1){
	dp[nd][0] = 0;
	for(int i = 1; i <= Ka; ++i)
		dp[nd][i] = INF;
	for(auto &i : adj[nd])
		if(i.ff != pr){
			dfs(i.ff, nd);
//			jogaby tazele
			for(int a1 = 0; a1 + i.ss <= Ka; ++a1){
				int a2 = Ka - a1 - i.ss;
				answer = min(answer, dp[nd][a1] + dp[i.ff][a2] + 1);
			}
//			dp-ni tazele
			for(int k = 0; k + i.ss <= Ka; ++k)
				dp[nd][k+i.ss] = min(dp[nd][k+i.ss], dp[i.ff][k] + 1);
		}
}

int best_path(int n, int k, int H[][2], int L[]){
	Ka = k;
	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(n <= 1e3 + 5){
		queue<int> q;
		for(int ad = 0; ad < n; ++ad){
			for(int i = 0; i <= n; ++i)
				vis[i] = 0, dis[i] = 0, edge[i] = 0;
			while(!q.empty())
				q.pop();
			q.push(ad);
			vis[ad] = 1;
			while(!q.empty()){
				int x = q.front();
				q.pop();
				for(auto &i : adj[x])
					if(!vis[i.ff]){
						vis[i.ff] = 1;
						q.push(i.ff);
						dis[i.ff] = dis[x] + i.ss;
						edge[i.ff] = edge[x] + 1;
					}
			}
//			dis[i] = ad-den i-e cenli uzaklyk
//			tree-da dine bir path bar
			for(int i = 0; i < n; ++i)
				if(dis[i] == k)
					answer = min(answer, edge[i]);	
		}
	}
	else if(k <= 100)
		dfs(1);
	return (answer == INF ? -1 : answer);
	assert(false);
}

//int H[MAX_N][2], L[MAX_N], solution;
//
//int main(){
//	int n, k;
//	scanf("%d%d", &n, &k);
//	for(int i = 0; i < n - 1; ++i) scanf("%d%d%d", &H[i][0], &H[i][1], &L[i]);
//	scanf("%d", &solution);
//	int answer = best_path(n, k, H, L);
//	if(answer == solution)
//		puts("Correct.");
//	else
//		printf("Incorrect. Returned %d, Expected %d.", answer, solution);
//	return 0;
//}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 13144 KB Output is correct
2 Correct 3 ms 13148 KB Output is correct
3 Correct 4 ms 13148 KB Output is correct
4 Correct 3 ms 13400 KB Output is correct
5 Correct 3 ms 13148 KB Output is correct
6 Correct 3 ms 13148 KB Output is correct
7 Correct 3 ms 13148 KB Output is correct
8 Correct 4 ms 13144 KB Output is correct
9 Correct 3 ms 13148 KB Output is correct
10 Correct 3 ms 13148 KB Output is correct
11 Correct 4 ms 13148 KB Output is correct
12 Correct 4 ms 13148 KB Output is correct
13 Correct 3 ms 13148 KB Output is correct
14 Correct 4 ms 13236 KB Output is correct
15 Correct 3 ms 13148 KB Output is correct
16 Correct 3 ms 13148 KB Output is correct
17 Correct 4 ms 13148 KB Output is correct
18 Correct 3 ms 13148 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 13144 KB Output is correct
2 Correct 3 ms 13148 KB Output is correct
3 Correct 4 ms 13148 KB Output is correct
4 Correct 3 ms 13400 KB Output is correct
5 Correct 3 ms 13148 KB Output is correct
6 Correct 3 ms 13148 KB Output is correct
7 Correct 3 ms 13148 KB Output is correct
8 Correct 4 ms 13144 KB Output is correct
9 Correct 3 ms 13148 KB Output is correct
10 Correct 3 ms 13148 KB Output is correct
11 Correct 4 ms 13148 KB Output is correct
12 Correct 4 ms 13148 KB Output is correct
13 Correct 3 ms 13148 KB Output is correct
14 Correct 4 ms 13236 KB Output is correct
15 Correct 3 ms 13148 KB Output is correct
16 Correct 3 ms 13148 KB Output is correct
17 Correct 4 ms 13148 KB Output is correct
18 Correct 3 ms 13148 KB Output is correct
19 Correct 3 ms 13148 KB Output is correct
20 Correct 3 ms 13148 KB Output is correct
21 Correct 13 ms 13332 KB Output is correct
22 Correct 14 ms 13144 KB Output is correct
23 Correct 14 ms 13144 KB Output is correct
24 Correct 13 ms 13340 KB Output is correct
25 Correct 13 ms 13148 KB Output is correct
26 Correct 13 ms 13148 KB Output is correct
27 Correct 12 ms 13340 KB Output is correct
28 Correct 13 ms 13148 KB Output is correct
29 Correct 12 ms 13148 KB Output is correct
30 Correct 15 ms 13148 KB Output is correct
31 Correct 12 ms 13336 KB Output is correct
32 Correct 13 ms 13144 KB Output is correct
33 Correct 15 ms 13144 KB Output is correct
34 Correct 10 ms 13148 KB Output is correct
35 Correct 9 ms 13148 KB Output is correct
36 Correct 8 ms 13148 KB Output is correct
37 Correct 8 ms 13148 KB Output is correct
38 Correct 10 ms 13144 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 13144 KB Output is correct
2 Correct 3 ms 13148 KB Output is correct
3 Correct 4 ms 13148 KB Output is correct
4 Correct 3 ms 13400 KB Output is correct
5 Correct 3 ms 13148 KB Output is correct
6 Correct 3 ms 13148 KB Output is correct
7 Correct 3 ms 13148 KB Output is correct
8 Correct 4 ms 13144 KB Output is correct
9 Correct 3 ms 13148 KB Output is correct
10 Correct 3 ms 13148 KB Output is correct
11 Correct 4 ms 13148 KB Output is correct
12 Correct 4 ms 13148 KB Output is correct
13 Correct 3 ms 13148 KB Output is correct
14 Correct 4 ms 13236 KB Output is correct
15 Correct 3 ms 13148 KB Output is correct
16 Correct 3 ms 13148 KB Output is correct
17 Correct 4 ms 13148 KB Output is correct
18 Correct 3 ms 13148 KB Output is correct
19 Correct 124 ms 58040 KB Output is correct
20 Correct 111 ms 59216 KB Output is correct
21 Correct 114 ms 58900 KB Output is correct
22 Correct 111 ms 59568 KB Output is correct
23 Correct 87 ms 59728 KB Output is correct
24 Correct 83 ms 59476 KB Output is correct
25 Correct 127 ms 67052 KB Output is correct
26 Correct 78 ms 67664 KB Output is correct
27 Correct 190 ms 103808 KB Output is correct
28 Correct 256 ms 120916 KB Output is correct
29 Correct 249 ms 114612 KB Output is correct
30 Correct 189 ms 104272 KB Output is correct
31 Correct 208 ms 104396 KB Output is correct
32 Correct 280 ms 105104 KB Output is correct
33 Correct 233 ms 104228 KB Output is correct
34 Correct 180 ms 103248 KB Output is correct

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 13144 KB Output is correct
2 Correct 3 ms 13148 KB Output is correct
3 Correct 4 ms 13148 KB Output is correct
4 Correct 3 ms 13400 KB Output is correct
5 Correct 3 ms 13148 KB Output is correct
6 Correct 3 ms 13148 KB Output is correct
7 Correct 3 ms 13148 KB Output is correct
8 Correct 4 ms 13144 KB Output is correct
9 Correct 3 ms 13148 KB Output is correct
10 Correct 3 ms 13148 KB Output is correct
11 Correct 4 ms 13148 KB Output is correct
12 Correct 4 ms 13148 KB Output is correct
13 Correct 3 ms 13148 KB Output is correct
14 Correct 4 ms 13236 KB Output is correct
15 Correct 3 ms 13148 KB Output is correct
16 Correct 3 ms 13148 KB Output is correct
17 Correct 4 ms 13148 KB Output is correct
18 Correct 3 ms 13148 KB Output is correct
19 Correct 3 ms 13148 KB Output is correct
20 Correct 3 ms 13148 KB Output is correct
21 Correct 13 ms 13332 KB Output is correct
22 Correct 14 ms 13144 KB Output is correct
23 Correct 14 ms 13144 KB Output is correct
24 Correct 13 ms 13340 KB Output is correct
25 Correct 13 ms 13148 KB Output is correct
26 Correct 13 ms 13148 KB Output is correct
27 Correct 12 ms 13340 KB Output is correct
28 Correct 13 ms 13148 KB Output is correct
29 Correct 12 ms 13148 KB Output is correct
30 Correct 15 ms 13148 KB Output is correct
31 Correct 12 ms 13336 KB Output is correct
32 Correct 13 ms 13144 KB Output is correct
33 Correct 15 ms 13144 KB Output is correct
34 Correct 10 ms 13148 KB Output is correct
35 Correct 9 ms 13148 KB Output is correct
36 Correct 8 ms 13148 KB Output is correct
37 Correct 8 ms 13148 KB Output is correct
38 Correct 10 ms 13144 KB Output is correct
39 Correct 124 ms 58040 KB Output is correct
40 Correct 111 ms 59216 KB Output is correct
41 Correct 114 ms 58900 KB Output is correct
42 Correct 111 ms 59568 KB Output is correct
43 Correct 87 ms 59728 KB Output is correct
44 Correct 83 ms 59476 KB Output is correct
45 Correct 127 ms 67052 KB Output is correct
46 Correct 78 ms 67664 KB Output is correct
47 Correct 190 ms 103808 KB Output is correct
48 Correct 256 ms 120916 KB Output is correct
49 Correct 249 ms 114612 KB Output is correct
50 Correct 189 ms 104272 KB Output is correct
51 Correct 208 ms 104396 KB Output is correct
52 Correct 280 ms 105104 KB Output is correct
53 Correct 233 ms 104228 KB Output is correct
54 Correct 180 ms 103248 KB Output is correct
55 Incorrect 5 ms 11516 KB Output isn't correct
56 Halted 0 ms 0 KB -