• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

question-closed Dlaczego mój program daje złe wyniki? Zadanie Łuk Triumfalny OI (drzewa)

0 głosów
77 wizyt
pytanie zadane 21 stycznia 2021 w Algorytmy przez wojtek_suchy Mądrala (6,790 p.)
zamknięte 21 stycznia 2021 przez wojtek_suchy

Mam takie zadanie: https://szkopul.edu.pl/proble[...]mxA6GujfX/site/?key=statement
No i lecę sobie DFS i sprawdzam w każdym wierzchołku czy potrzebuje dodatkowych robotników, program daje błędny wynik dopiero w testach gdy n > 1000 więc trudno coś takiego debuggować. Program zwraca zbyt mały wynik np. potrzeba 6 robotników a mój program zwraca 5. Czy ktoś pomógłby mi znaleźć relatywnie małe testy dla których mój program daje błędne odpowiedzi?

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long

#define fi first
#define se second

#define FOR(x, y, z) for (int z = x; z < y; z++)
#define FORD(x, y, z) for (int z = x; z > y; z--)

const int MAXN = 3e5 + 7;
vector<vector<int>> graph(MAXN);
int min_need_workers = 0;

void dfs(int p, int idx, int deep, int prev_need_bows_to_build, int act_workers){
    while((int)graph[idx].size()-(p!=-1) + prev_need_bows_to_build > act_workers * deep)
        act_workers++;
    for (auto child : graph[idx]){
        if (child != p)
            dfs(idx, child, deep+1, prev_need_bows_to_build+graph[idx].size()-(p!=-1), act_workers);
    }
    min_need_workers = max(min_need_workers, act_workers);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    int n, a, b;
    cin >> n;
    FOR(0, n-1, i){
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    dfs(-1, 1, 1, 0, 0);

    cout << min_need_workers << "\n";

    return 0;
}
komentarz zamknięcia: Źle zrozumiałem treść zadania

1 odpowiedź

0 głosów
odpowiedź 21 stycznia 2021 przez Wiciorny Mędrzec (196,600 p.)
W tego typu zadanich, gdzie operacje na liczbach mogą być duże zwykle problem leży w tym, że operujesz na int a nie np double, czy float. gdyż ich zakres jest większy.
Tym bardziej, że warunek rzutujesz na int, co może powodować ucinanie pewnych wartości
komentarz 21 stycznia 2021 przez wojtek_suchy Mądrala (6,790 p.)
Niestety nie :(, wszystko mieści się w zakresach, a teraz  nawet znalazłem błędy test:

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

Podobne pytania

0 głosów
1 odpowiedź 109 wizyt
pytanie zadane 5 stycznia 2017 w Rozwój zawodowy, nauka, szkoła, praca przez Poeta Doctus Użytkownik (720 p.)
0 głosów
2 odpowiedzi 194 wizyt
pytanie zadane 1 listopada 2016 w C i C++ przez sulas99 Początkujący (340 p.)
0 głosów
1 odpowiedź 105 wizyt

86,427 zapytań

135,188 odpowiedzi

300,309 komentarzy

57,184 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...