Zadanie Łuk triumfalny

Question

Link do zadania: https://szkopul.edu.pl/problemset/problem/jgCcEjQu3kdpM4BmxA6GujfX/site/?key=statement

Mój program działa podobnie jak wzorcówka, z tym że idzie od korzenia do liści zamiast odwrotnie. Mimo tego, że nie znalazłem żadnego przypadku gdzie by nie działał to i tak daje 30pkt. Jeśli ktoś znalazł jakiś przykład, w którym mój kod nie zadziała to bardzo by mi to pomogło.

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <string>
#include <queue>
#include <fstream>
#include <cmath>
#include<bitset>
#include <array>
#include <stack>
#include<iomanip>
#include <deque>
 
 
 
using namespace std;
using ll = long long;
using ld = long double;
 
 
 
const ll mod1 = 998244353;
const ll mod2 = 1e9 + 7;
const int MAXN = 3e5 + 222;
const int K = 27;
const ll pp = 307;
const int ZERO = 1e5;
 
 
ll n,lim,flag;
vector<int> adj[MAXN];
ll dp[MAXN];
 
void dfs(int v, int p)
{
    ll children = adj[v].size()-1 + (v==1);
    dp[v] += lim;
    dp[v] = min((ll)n, dp[v]);
    if (dp[v] < children)
        flag = 1;
    ll rem = dp[v] - children;
 
    for (auto u : adj[v])
    {
        if (u == p)continue;
        dp[u] += rem;
        dfs(u, v);
    }
     
}
 
 
 
 
bool check(ll x)
{
    fill(dp, dp + n + 3, 0);
    lim = x;
    flag = 0;
 
    dfs(1, 1);
 
    //cout<<flag<<endl;
 
    return !flag;
}
 
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
 
    cin >> n;
 
 
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
 
 
 
    ll l = 0, r = 3e5;
 
    while (l < r)
    {
        ll m = (l + r) / 2;
        if (check(m))
            r = m;
        else
            l = m + 1;
    }
 
 
 
    cout << l << '\n';
 
 
 
 
 
 
 
 
    return 0;
}

 

 

Comments

a co oznacza w twoim kodzie dp[i]?

Bo jak idziesz od dołu kolejnościa post-order, to dp[i] oznacza ile musisz ulozyc wczesniej luków triumfalnych w poddrzewie zaczynającym się w i, gdy wejdziesz do wierzchołka i.

---

już się domyśliłem.

Answer 1

Problem w twoim kodzie, jest taki, że np. Jeśli k = 3, i od korzenia(jedynki) wychodzą 2 krawędzie, to dajesz obydu zapas 1, czyl idą do wszystkich synów zapas 1, a nie może tak być bo zapasu masz łącznie 1, a nie ile_synów * zapas(zmienna rem to zapas z tego co zrozumiałem). I generujesz sztucznie zapas, który nie istnieje i robią się za małe wyniki. Nie wiem czy da się to zrobić innaczej niż wzorcówka od synów.

btw, jak robiłem niedawno to zadanie, to też długo nie mogłem zrozumieć dlaczego to nie wchodzi. To zadanie jest bardzo trudne.

Comments

Już coś zaczynam rozumieć. Dalej nie wiem czemu różnica między ile_synów * zapas , a zapas ma znaczenie, skoro zapas i tak będzie rozpatrywany z jednego syna, a nie z kilku.

---

Popatrz się na taki przykład:

17
1 2
2 3
3 4
3 5
3 6
3 7
3 8
3 9
1 10
10 11
11 12
11 13
11 14
11 15
11 16
11 17

Twój kod daje 3 a powinno 4. Dajesz z jedynki do synów i zostało Ci 1 zapasu. I teraz musisz go gdzieś dać. Nie ma tak, że ty sobie go zostawisz i wykorzystasz kiedy Ci się podoba. Robota ma być zrobiona w całym dniu, a nie tak, że sobie uzbierasz 10 zapasu i go wykorzystasz podczas jednego dnia.

Rozwiązanie od dołu, załozeniem, ze dp[i] = max(0, suma po dp synow + ile_synow - k) załatwia ten problem.

---

Te 10 zapasu traktowałem jako: jeśli wchodzimy do jakiegoś poddrzewa i mamy te 10 zapasu to możemy założyć, że już wcześniej to wybudowaliśmy w synach, a nie, że na bieżąco wybieram dzień, w którym nagle te 10 zużywam.