Submission #1029363

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1029363	2024-07-20 18:57:13	MDario	The Xana coup (BOI21_xanadu)	C++17	100 / 100	36 ms	17236 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>
using namespace std;
#define F first
#define S second
typedef long long ll;
typedef pair<pair<ll, ll>, pair<ll, ll>> Ans;
const string noyes[2] = {"NO", "YES"};
const ll INFLL = (1ll << 62);
const int INF = (1 << 30);
const int MAXN = 100'001;
const ll MOD = 1'000'000'007;
vector<int> g[MAXN];
int a[MAXN];
Ans f(int x, int ax) {
  // Valor inicial dependiendo de si este nodo estaba o no encendido
  // inicialmente
  Ans y = {{INF, 1}, {0, INF}};
  if (a[x])
    y = {{0, INF}, {INF, 1}};
  for (int i : g[x]) {
    if (i != ax) {
      // temporal y
      Ans ty = f(i, x);
      y = {{min(y.F.F + ty.S.F, y.S.F + ty.S.S),
            min(y.F.S + ty.F.F, y.S.S + ty.F.S)},
           {min(y.S.F + ty.S.F, y.F.F + ty.S.S),
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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