Submission #1133732

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1133732	2025-01-08 17:46:25	PagodePaiva	Road Closures (APIO21_roads)	C++17	24 / 100	360 ms	65860 KiB

roads

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>
#include "roads.h"
#include <vector>
#define ll long long
using namespace std;
const ll N = 2010;
const ll inf = 1e18/N;
vector <pair<ll, ll>> g[N];
ll dp[N][N][2];
void solve(ll p, ll v, ll k, ll fg){
  if(dp[v][k][fg] != -1) return;
  ll sum = 0;
  vector <ll> best;
  for(auto [x, w] : g[v]){
    if(x == p) continue;
    solve(v, x, k, 0);
    solve(v, x, k, 1);
    sum += dp[x][k][0];
    best.push_back(dp[x][k][1]-dp[x][k][0]+w);
  }
  ll deg = g[v].size();
  deg -= fg;
  sort(best.begin(), best.end());
  reverse(best.begin(), best.end());
  while(deg > k or (!best.empty() ? best.back() <= 0 : false)){
    if(best.empty()) break;
    sum += best.back();
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22