제출 #545360

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
545360	2022-04-04 10:51:44	tibinyte	Parkovi (COCI22_parkovi)	C++14	110 / 110	1536 ms	44324 KiB

Main

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#define inf 1e16
using namespace std;
ifstream fin("geana.in");
ofstream fout("geana.out");
long long n, k;
vector<pair<long long, long long>> g[200001];
vector<int> sol;
long long deep[200001], closest[200001];
long long ans;
void dfs(long long node, long long parent, long long lim, long long cost, bool reconst) {
  closest[node] = inf;
  deep[node] = -inf;
  for (auto i : g[node]) {
    if (i.first != parent) {
      dfs(i.first, node, lim, i.second, reconst);
      deep[node] = max(deep[node], deep[i.first] + i.second);
      closest[node] = min(closest[node], closest[i.first] + i.second);
    }
  }
  if (closest[node] > lim && deep[node] < 0) {
    deep[node] = 0;
  }
  if (deep[node] + closest[node] <= lim) {
    deep[node] = -inf;
    return;
  }
  if (deep[node] + cost > lim || (node==1&&(deep[node] >= 0))) {
    if (reconst) {
      sol.push_back(node);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60