제출 #831985

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
831985		serifefedartar	Race (IOI11_race)	C++17	0 / 100	128 ms	80244 KiB

race

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 18
#define MAXN 1000005

vector<vector<pair<int,int>>> graph;
vector<int> sz, marked;
int mn[MAXN];
int req_len;
int ans = 1e8;
int get_sz(int node, int parent) {
	sz[node] = 1;
	for (auto u : graph[node]) {
		if (u.f != parent && !marked[u.f])
			sz[node] += get_sz(u.f, node);
	}
	return sz[node];
}

int find_centro(int node, int parent, int n) {
	for (auto u : graph[node]) {
		if (u.f != parent && !marked[u.f] && sz[u.f] * 2 > n)
			return find_centro(u.f, node, n);
	}
	return node;
}

void eval(int node, int parent, int dist, int edges) {
	if (dist > req_len)
		return ;
	ans = min(ans, mn[req_len - dist] + edges);
	for (auto u : graph[node]) {
		if (u.f != parent && !marked[u.f])
			eval(u.f, node, dist + u.s, edges + 1);
	}
}

void add(int node, int parent, int dist, int edges) {
	mn[dist] = min(mn[dist], edges);
	for (auto u : graph[node]) {
		if (u.f != parent && !marked[u.f])
			add(u.f, node, dist + u.s, edges + 1);
	}
}

void solve(int node, int parent) {
	int n = get_sz(node, parent);
	int centro = find_centro(node, parent, n);

	fill(mn, mn + n + 10, 1e9);
	for (auto u : graph[centro]) {
		if (!marked[u.f]) {
			eval(u.f, centro, u.s, 1);
			add(u.f, centro, u.s, 1);
		}
	}

	marked[centro] = true;
	for (auto u : graph[centro]) {
		if (u.f != parent && !marked[u.f])
			solve(u.f, node);
	}
}

int best_path(int N, int K, int H[][2], int L[]) {
	req_len = K;
	int a, b;
	graph = vector<vector<pair<int,int>>>(N, vector<pair<int,int>>());
	sz = vector<int>(N);
	marked = vector<int>(N, false);
	for (int i = 0; i < N-1; i++) {
		cin >> a >> b;
		graph[a].push_back({b, L[i]});
		graph[b].push_back({a, L[i]});
	}
	solve(1, 1);
	cout << (ans == 1e8 ? -1 : ans) << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:84:1: warning: no return statement in function returning non-void [-Wreturn-type]
   84 | }
      | ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57