Submission #983481

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
983481	2024-05-15 14:33:36	OAleksa	The Xana coup (BOI21_xanadu)	C++14	100 / 100	63 ms	23548 KiB

xanadu

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 f first
#define s second
using namespace std;
#define int long long
const int N = 1e5 + 69;
const int inf = 1e9 + 69;
int n, dp[N][2][2], a[N];
vector<int> g[N];
void dfs(int v, int p) {
  vector<int> ch;
  for (auto u : g[v]) {
    if (u == p)
      continue;
    dfs(u, v);
    ch.push_back(u);
  }
  if (ch.empty()) {
    dp[v][a[v]][0] = 0;
    dp[v][a[v] ^ 1][1] = 1;
    dp[v][a[v]][1] = dp[v][a[v] ^ 1][0] = inf;
  }
  else {
    int uk1 = 0, uk2 = 0;
    int mn1 = inf, mn2 = inf, c = 0;
    for (auto u : ch) {
      uk1 += min(dp[u][0][0], dp[u][0][1]);
      if (dp[u][0][0] <= dp[u][0][1])
        mn1 = min(mn1, dp[u][0][1] - dp[u][0][0]);
      if (dp[u][0][1] <= dp[u][0][0]) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40
• Subtask 5: 30 / 30