Submission #528947

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
528947	2022-02-21 19:56:25	penguinhacker	Parkovi (COCI22_parkovi)	C++14	110 / 110	1330 ms	34256 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>
using namespace std;
#define ll long long
#define ar array
const int mxN=2e5;
int n, k;
vector<ar<int, 2>> adj[mxN];
ll lim, need[mxN], extra[mxN];
bool used[mxN];
void dfs(int u=0, int p=-1) {
  need[u]=0, extra[u]=-1;
  for (ar<int, 2> v : adj[u]) {
    if (v[0]==p)
      continue;
    dfs(v[0], u);
    if (extra[v[0]]!=-1) {
      if (extra[v[0]]>=v[1])
        extra[u]=max(extra[u], extra[v[0]]-v[1]);
    } else {
      if (need[v[0]]+v[1]>lim) {
        used[v[0]]=1;
        extra[v[0]]=lim;
        if (lim>=v[1])
          extra[u]=max(extra[u], lim-v[1]);
      } else
        need[u]=max(need[u], need[v[0]]+v[1]);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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