oj.uz

답안 #161227

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
161227 2019-11-01T13:50:51 Z Juney 경주 (Race) (IOI11_race) C++14
43 / 100
 542 ms 30300 KB 
#include "race.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define all(x) ((x).begin(), (x).end())

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5 + 5;
const int INF = 1e9;
const ll MOD = 1e9 + 7;

int N, sz[MAXN], ans, K;
vector<pll> G[MAXN];
bool del[MAXN];
map<int, int> mp;

int szdfs(int cur, int par) {
	sz[cur] = 1;
	for(auto i : G[cur]) if(!del[i.fi] && i.fi != par) sz[cur] += szdfs(i.fi, cur);
	return sz[cur];
}

int cdfs(int cur, int par, int cap) {
	for(auto i : G[cur]) if(!del[i.fi] && i.fi != par && sz[i.fi] > cap) return cdfs(i.fi, cur, cap);
	return cur;
}

void dfs(int cur, int par, int dis, int cnt) {
	if(dis > K) return;
	if(dis == K || mp[K - dis]) ans = min(ans, mp[K - dis] + cnt);
	for(auto nxt : G[cur]) if(!del[nxt.fi] && nxt.fi != par) dfs(nxt.fi, cur, dis + nxt.se, cnt+1);
	if(mp[dis] == 0) mp[dis] = cnt;
	else mp[dis] = min(mp[dis], cnt);
}

void solve(int cur) {
	mp.clear();
	for(auto nxt : G[cur]) if(!del[nxt.fi]) dfs(nxt.fi, cur, nxt.se, 1); 
}

void decompose(int root, int par) {
	int cap = szdfs(root, par);
	int cen = cdfs(root, par, cap / 2);
	del[cen] = 1;
	solve(cen);
	for(auto i : G[cen]) if(!del[i.fi]) decompose(i.fi, cen);
}

int best_path(int _N, int _K, int H[][2], int L[]) {
	N = _N; K = _K;
	for(int i=0; i<N-1; i++) {
		int a = H[i][0]+1, b = H[i][1]+1, c = L[i];
		G[a].push_back(pll(b, c)); G[b].push_back(pll(a, c));
	}
	ans = 1e9;
	decompose(1, 0);
	if(ans == 1e9) return -1;
	return ans;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 8 ms 5112 KB Output is correct
4 Correct 12 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 8 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 7 ms 4984 KB Output is correct
11 Correct 6 ms 4984 KB Output is correct
12 Correct 7 ms 4984 KB Output is correct
13 Correct 7 ms 5084 KB Output is correct
14 Correct 6 ms 4984 KB Output is correct
15 Correct 7 ms 4984 KB Output is correct
16 Correct 6 ms 4984 KB Output is correct
17 Correct 7 ms 4952 KB Output is correct
18 Correct 6 ms 5112 KB Output is correct
19 Correct 6 ms 4984 KB Output is correct
20 Correct 6 ms 4984 KB Output is correct
21 Correct 9 ms 5196 KB Output is correct
22 Correct 8 ms 5116 KB Output is correct
23 Correct 8 ms 5240 KB Output is correct
24 Correct 8 ms 5112 KB Output is correct
25 Correct 9 ms 5244 KB Output is correct
26 Correct 7 ms 5088 KB Output is correct
27 Correct 7 ms 5112 KB Output is correct
28 Correct 9 ms 5240 KB Output is correct
29 Correct 9 ms 5240 KB Output is correct
30 Correct 9 ms 5240 KB Output is correct
31 Correct 9 ms 5244 KB Output is correct
32 Correct 9 ms 5240 KB Output is correct
33 Correct 10 ms 5368 KB Output is correct
34 Correct 8 ms 5112 KB Output is correct
35 Correct 8 ms 5112 KB Output is correct
36 Correct 8 ms 5112 KB Output is correct
37 Correct 9 ms 5112 KB Output is correct
38 Correct 9 ms 5240 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 8 ms 5112 KB Output is correct
4 Correct 12 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 8 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 7 ms 4984 KB Output is correct
11 Correct 6 ms 4984 KB Output is correct
12 Correct 7 ms 4984 KB Output is correct
13 Correct 7 ms 5084 KB Output is correct
14 Correct 6 ms 4984 KB Output is correct
15 Correct 7 ms 4984 KB Output is correct
16 Correct 6 ms 4984 KB Output is correct
17 Correct 7 ms 4952 KB Output is correct
18 Correct 6 ms 5112 KB Output is correct
19 Correct 319 ms 13244 KB Output is correct
20 Correct 284 ms 13280 KB Output is correct
21 Correct 304 ms 13260 KB Output is correct
22 Correct 287 ms 13304 KB Output is correct
23 Correct 140 ms 13688 KB Output is correct
24 Correct 121 ms 12940 KB Output is correct
25 Correct 239 ms 15228 KB Output is correct
26 Correct 147 ms 17400 KB Output is correct
27 Correct 321 ms 22252 KB Output is correct
28 Correct 471 ms 30300 KB Output is correct
29 Correct 508 ms 29732 KB Output is correct
30 Correct 320 ms 22008 KB Output is correct
31 Correct 324 ms 22008 KB Output is correct
32 Correct 355 ms 22208 KB Output is correct
33 Correct 542 ms 20880 KB Output is correct
34 Correct 338 ms 21688 KB Output is correct

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 8 ms 5112 KB Output is correct
4 Correct 12 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 8 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 7 ms 4984 KB Output is correct
11 Correct 6 ms 4984 KB Output is correct
12 Correct 7 ms 4984 KB Output is correct
13 Correct 7 ms 5084 KB Output is correct
14 Correct 6 ms 4984 KB Output is correct
15 Correct 7 ms 4984 KB Output is correct
16 Correct 6 ms 4984 KB Output is correct
17 Correct 7 ms 4952 KB Output is correct
18 Correct 6 ms 5112 KB Output is correct
19 Correct 6 ms 4984 KB Output is correct
20 Correct 6 ms 4984 KB Output is correct
21 Correct 9 ms 5196 KB Output is correct
22 Correct 8 ms 5116 KB Output is correct
23 Correct 8 ms 5240 KB Output is correct
24 Correct 8 ms 5112 KB Output is correct
25 Correct 9 ms 5244 KB Output is correct
26 Correct 7 ms 5088 KB Output is correct
27 Correct 7 ms 5112 KB Output is correct
28 Correct 9 ms 5240 KB Output is correct
29 Correct 9 ms 5240 KB Output is correct
30 Correct 9 ms 5240 KB Output is correct
31 Correct 9 ms 5244 KB Output is correct
32 Correct 9 ms 5240 KB Output is correct
33 Correct 10 ms 5368 KB Output is correct
34 Correct 8 ms 5112 KB Output is correct
35 Correct 8 ms 5112 KB Output is correct
36 Correct 8 ms 5112 KB Output is correct
37 Correct 9 ms 5112 KB Output is correct
38 Correct 9 ms 5240 KB Output is correct
39 Correct 319 ms 13244 KB Output is correct
40 Correct 284 ms 13280 KB Output is correct
41 Correct 304 ms 13260 KB Output is correct
42 Correct 287 ms 13304 KB Output is correct
43 Correct 140 ms 13688 KB Output is correct
44 Correct 121 ms 12940 KB Output is correct
45 Correct 239 ms 15228 KB Output is correct
46 Correct 147 ms 17400 KB Output is correct
47 Correct 321 ms 22252 KB Output is correct
48 Correct 471 ms 30300 KB Output is correct
49 Correct 508 ms 29732 KB Output is correct
50 Correct 320 ms 22008 KB Output is correct
51 Correct 324 ms 22008 KB Output is correct
52 Correct 355 ms 22208 KB Output is correct
53 Correct 542 ms 20880 KB Output is correct
54 Correct 338 ms 21688 KB Output is correct
55 Correct 36 ms 6136 KB Output is correct
56 Incorrect 26 ms 5920 KB Output isn't correct
57 Halted 0 ms 0 KB -