oj.uz

답안 #383543

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
383543 2021-03-30T09:12:41 Z ace_in_the_hole 경주 (Race) (IOI11_race) C++14
43 / 100
 639 ms 117612 KB 
#include "race.h"

#include<bits/stdc++.h>
using namespace std;

#define push_back emplace_back

typedef long long Int;
typedef long double Real;

const int MOD = 2004010501;//>2e9

const int INF = 1e9;
const int MIN = 1005;
const int MAX = 2e5 + 500;

struct Edge {
	int to, weight;
	Edge(int to, int weight) : to(to), weight(weight) {}
};
vector<Edge> adj[MAX];

int answer = INF, num_nodes, capa;
void minimize(int& var, const int& val) {
	if (val < var) var = val;
}

namespace Subtask2 {
	int weight[MIN][MIN], dist[MIN][MIN];
	void process() {
		for (int u = 0; u < num_nodes; u++) {
			for (int v = 0; v < num_nodes; v++) 
				weight[u][v] = dist[u][v] = -1;
				
			queue<int> vis_list;
			vis_list.push(u);
			weight[u][u] = dist[u][u] = 0;
			
			while (!vis_list.empty()) {
				int cur = vis_list.front(); vis_list.pop();
				if (weight[u][cur] >= capa) continue;
				for (auto edge : adj[cur]) {
					const int& nxt = edge.to;
					const int& w = edge.weight;
					if (dist[u][nxt] != -1) continue;
					dist[u][nxt] = dist[u][cur] + 1;
					weight[u][nxt] = weight[u][cur] + w;
					vis_list.push(nxt); 
				}
			}
			
			for (int v = 0; v < num_nodes; v++)
				if (weight[u][v] == capa) minimize(answer, dist[u][v]);
		}
	}
}

namespace Subtask3 {
	int dp[MAX][105];
	
	void calc(int u, int pa) {
		dp[u][0] = 0; 
		for (int x = 1; x <= capa; x++) dp[u][x] = INF;
		
		for (auto edge : adj[u]) {
			const int& v = edge.to;
			const int& w = edge.weight;
			if (v == pa) continue; calc(v, u);
			
			for (int y = 0; y <= capa - w; y++) {
				int remain = capa - (y + w);
				if (remain >= 0)
					minimize(answer, dp[u][remain] + dp[v][y] + 1);
			}
			
			for (int y = 0; y <= capa - w; y++) 
				minimize(dp[u][w + y], dp[v][y] + 1);
		}
		minimize(answer, dp[u][capa]);
	}
	
};

void solve() {
	if (num_nodes < MIN) Subtask2 :: process(); else
	Subtask3 :: calc(0, -1);
	if (answer == INF) answer = -1;
}

int best_path(int N, int K, int H[][2], int L[]) {
	::num_nodes = N;
	::capa = K;
	for (int i = 0; i < N; i++) 
		adj[H[i][0]].push_back(Edge(H[i][1], L[i])),
		adj[H[i][1]].push_back(Edge(H[i][0], L[i]));
		
	solve();

	return answer;
}

Compilation message

race.cpp: In function 'void Subtask3::calc(int, int)':
race.cpp:68:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   68 |    if (v == pa) continue; calc(v, u);
      |    ^~
race.cpp:68:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   68 |    if (v == pa) continue; calc(v, u);
      |                           ^~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5868 KB Output is correct
2 Correct 5 ms 5868 KB Output is correct
3 Correct 5 ms 5868 KB Output is correct
4 Correct 5 ms 5868 KB Output is correct
5 Correct 4 ms 5868 KB Output is correct
6 Correct 5 ms 5868 KB Output is correct
7 Correct 4 ms 5868 KB Output is correct
8 Correct 4 ms 5868 KB Output is correct
9 Correct 5 ms 5868 KB Output is correct
10 Correct 5 ms 5868 KB Output is correct
11 Correct 5 ms 5868 KB Output is correct
12 Correct 5 ms 5868 KB Output is correct
13 Correct 5 ms 5868 KB Output is correct
14 Correct 6 ms 5884 KB Output is correct
15 Correct 5 ms 5888 KB Output is correct
16 Correct 5 ms 5868 KB Output is correct
17 Correct 5 ms 5868 KB Output is correct
18 Correct 5 ms 5868 KB Output is correct
19 Correct 4 ms 5100 KB Output is correct
20 Correct 5 ms 5868 KB Output is correct
21 Correct 27 ms 13036 KB Output is correct
22 Correct 10 ms 12908 KB Output is correct
23 Correct 11 ms 12908 KB Output is correct
24 Correct 11 ms 12908 KB Output is correct
25 Correct 27 ms 13036 KB Output is correct
26 Correct 11 ms 12916 KB Output is correct
27 Correct 11 ms 12908 KB Output is correct
28 Correct 15 ms 13036 KB Output is correct
29 Correct 20 ms 13036 KB Output is correct
30 Correct 21 ms 13036 KB Output is correct
31 Correct 26 ms 13036 KB Output is correct
32 Correct 27 ms 13056 KB Output is correct
33 Correct 24 ms 12908 KB Output is correct
34 Correct 13 ms 12396 KB Output is correct
35 Correct 11 ms 12140 KB Output is correct
36 Correct 10 ms 11628 KB Output is correct
37 Correct 19 ms 11628 KB Output is correct
38 Correct 24 ms 12396 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5868 KB Output is correct
2 Correct 5 ms 5868 KB Output is correct
3 Correct 5 ms 5868 KB Output is correct
4 Correct 5 ms 5868 KB Output is correct
5 Correct 4 ms 5868 KB Output is correct
6 Correct 5 ms 5868 KB Output is correct
7 Correct 4 ms 5868 KB Output is correct
8 Correct 4 ms 5868 KB Output is correct
9 Correct 5 ms 5868 KB Output is correct
10 Correct 5 ms 5868 KB Output is correct
11 Correct 5 ms 5868 KB Output is correct
12 Correct 5 ms 5868 KB Output is correct
13 Correct 5 ms 5868 KB Output is correct
14 Correct 6 ms 5884 KB Output is correct
15 Correct 5 ms 5888 KB Output is correct
16 Correct 5 ms 5868 KB Output is correct
17 Correct 5 ms 5868 KB Output is correct
18 Correct 5 ms 5868 KB Output is correct
19 Correct 294 ms 50924 KB Output is correct
20 Correct 286 ms 52332 KB Output is correct
21 Correct 286 ms 52332 KB Output is correct
22 Correct 298 ms 52460 KB Output is correct
23 Correct 216 ms 52844 KB Output is correct
24 Correct 215 ms 52588 KB Output is correct
25 Correct 308 ms 56812 KB Output is correct
26 Correct 184 ms 61292 KB Output is correct
27 Correct 479 ms 99848 KB Output is correct
28 Correct 608 ms 117612 KB Output is correct
29 Correct 592 ms 116588 KB Output is correct
30 Correct 479 ms 99564 KB Output is correct
31 Correct 498 ms 99692 KB Output is correct
32 Correct 639 ms 99564 KB Output is correct
33 Correct 561 ms 98540 KB Output is correct
34 Correct 358 ms 99308 KB Output is correct

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5868 KB Output is correct
2 Correct 5 ms 5868 KB Output is correct
3 Correct 5 ms 5868 KB Output is correct
4 Correct 5 ms 5868 KB Output is correct
5 Correct 4 ms 5868 KB Output is correct
6 Correct 5 ms 5868 KB Output is correct
7 Correct 4 ms 5868 KB Output is correct
8 Correct 4 ms 5868 KB Output is correct
9 Correct 5 ms 5868 KB Output is correct
10 Correct 5 ms 5868 KB Output is correct
11 Correct 5 ms 5868 KB Output is correct
12 Correct 5 ms 5868 KB Output is correct
13 Correct 5 ms 5868 KB Output is correct
14 Correct 6 ms 5884 KB Output is correct
15 Correct 5 ms 5888 KB Output is correct
16 Correct 5 ms 5868 KB Output is correct
17 Correct 5 ms 5868 KB Output is correct
18 Correct 5 ms 5868 KB Output is correct
19 Correct 4 ms 5100 KB Output is correct
20 Correct 5 ms 5868 KB Output is correct
21 Correct 27 ms 13036 KB Output is correct
22 Correct 10 ms 12908 KB Output is correct
23 Correct 11 ms 12908 KB Output is correct
24 Correct 11 ms 12908 KB Output is correct
25 Correct 27 ms 13036 KB Output is correct
26 Correct 11 ms 12916 KB Output is correct
27 Correct 11 ms 12908 KB Output is correct
28 Correct 15 ms 13036 KB Output is correct
29 Correct 20 ms 13036 KB Output is correct
30 Correct 21 ms 13036 KB Output is correct
31 Correct 26 ms 13036 KB Output is correct
32 Correct 27 ms 13056 KB Output is correct
33 Correct 24 ms 12908 KB Output is correct
34 Correct 13 ms 12396 KB Output is correct
35 Correct 11 ms 12140 KB Output is correct
36 Correct 10 ms 11628 KB Output is correct
37 Correct 19 ms 11628 KB Output is correct
38 Correct 24 ms 12396 KB Output is correct
39 Correct 294 ms 50924 KB Output is correct
40 Correct 286 ms 52332 KB Output is correct
41 Correct 286 ms 52332 KB Output is correct
42 Correct 298 ms 52460 KB Output is correct
43 Correct 216 ms 52844 KB Output is correct
44 Correct 215 ms 52588 KB Output is correct
45 Correct 308 ms 56812 KB Output is correct
46 Correct 184 ms 61292 KB Output is correct
47 Correct 479 ms 99848 KB Output is correct
48 Correct 608 ms 117612 KB Output is correct
49 Correct 592 ms 116588 KB Output is correct
50 Correct 479 ms 99564 KB Output is correct
51 Correct 498 ms 99692 KB Output is correct
52 Correct 639 ms 99564 KB Output is correct
53 Correct 561 ms 98540 KB Output is correct
54 Correct 358 ms 99308 KB Output is correct
55 Incorrect 425 ms 9860 KB Output isn't correct
56 Halted 0 ms 0 KB -