oj.uz

답안 #997852

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
997852 2024-06-13T03:39:38 Z icchou233 경주 (Race) (IOI11_race) C++17
0 / 100
 1 ms 2396 KB 
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int,int>;
#define all(a) begin(a), end(a)
#define rall(a) rbegin(a), rend(a)
#define f first
#define s second
int minDist = INT_MAX;
void dfs(int e, int p, int k, vector<vector<PII>> &edges, vector<map<int,int>> &cnt) {
	cnt[e][0] = 0;
	for (PII v: edges[e]) {
		if (v.f == p) continue;
		dfs(v.f, e, k, edges, cnt);
		for (auto it = rbegin(cnt[v.f]); it != rend(cnt[v.f]); it = prev(it)) {
			PII c = *it;
			cnt[v.f].erase(c.f);
			if (c.f + v.s <= k) {
				if (c.f + v.s == k) {
					minDist = min(minDist, c.s + 1);
				}
				cnt[v.f][c.f + v.s] = c.s + 1;
			}
			if (c.f == 0) break;
		}
		if (cnt[e].size() < cnt[v.f].size()) {
			cnt[e].swap(cnt[v.f]);
		}
		for (PII a: cnt[v.f]) {
			if (cnt[e].count(k - a.f) > 0) {
				minDist = min(minDist, cnt[v.f][a.f] + cnt[e][k - a.f]);
			}
			if (cnt[e].count(a.f) > 0) {
				cnt[e][a.f] = min(cnt[e][a.f], cnt[v.f][a.f]);
			}
			else {
				cnt[e][a.f] = cnt[v.f][a.f];
			}
		}
	}
}
int best_path(int N, int K, int H[][2], int L[]) {
	vector<vector<PII>> edges(N);
	for (int i = 0; i < N - 1; i++) {
		edges[H[i][0]].push_back({H[i][1], L[i]});
		edges[H[i][1]].push_back({H[i][0], L[i]});
	}
	vector<map<int,int>> cnt(N);
	dfs(0, -1, K, edges, cnt);
	return minDist == INT_MAX? -1: minDist;
}

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -