8982 2024. 02. 09 21:55:28 Vkrisztian01 Testvérvárosok cpp17 Futási hiba 0/100 268ms 524692 KiB
#include <iostream>
#include <vector>
#include <deque>
using namespace std;



int n,k,a,b;
vector<vector<int>> g;

int64_t   osszefesul(deque<int>& a, deque<int>& b)
 {
    if (a.size() < b.size()) swap(a, b);
    int egyikmeret = a.size();
      int masikmeret = b.size();

    int64_t ki = 0;
    for (int i = max(0, (k-    masikmeret) + 1); i < min(k +1,egyikmeret); i++)
{
        ki += a[i] * b[k-i];
    }
    for (int i = 0; i < masikmeret; i++) a[i] += b[i];
    return ki;
}

pair<int64_t, deque<int>> f(int csucs,int szulo)
{
    pair<int64_t, deque<int>> seged;
    seged.first=0;
    seged.second.push_back(1);
    for (auto to : g[csucs])
        {
        if (to == szulo) continue;
        pair<int64_t,deque<int> > gyerkoc= f(to, csucs);
        gyerkoc.second.push_front(0);
        seged.first += gyerkoc.first + osszefesul(seged.second, gyerkoc.second);
        if(seged.second.size()>k)
        {
            seged.second[0]+=seged.second[k];
            seged.second.pop_back();
        }
        }
    return seged;
}

int main()
{
    	cin.tie(0);
	ios::sync_with_stdio(false);
    cin >> n >> k;
    g.resize(n+1);
    for (int i = 0; i < n-1; ++i) {
                cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    cout<<f(1,0).first;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1956 KiB
2 Futási hiba 218ms 524692 KiB
subtask2 0/15
3 Futási hiba 4ms 2804 KiB
4 Hibás válasz 3ms 2908 KiB
5 Futási hiba 4ms 3520 KiB
6 Futási hiba 3ms 3116 KiB
7 Futási hiba 3ms 3136 KiB
8 Futási hiba 263ms 523832 KiB
9 Futási hiba 194ms 523784 KiB
subtask3 0/15
10 Futási hiba 219ms 523744 KiB
11 Hibás válasz 4ms 3600 KiB
12 Futási hiba 222ms 523484 KiB
13 Hibás válasz 17ms 8516 KiB
14 Futási hiba 226ms 523192 KiB
subtask4 0/20
15 Futási hiba 4ms 4044 KiB
16 Futási hiba 204ms 523188 KiB
17 Futási hiba 189ms 523080 KiB
18 Futási hiba 197ms 523040 KiB
19 Futási hiba 200ms 523068 KiB
20 Futási hiba 202ms 523064 KiB
21 Futási hiba 202ms 523064 KiB
22 Futási hiba 204ms 523060 KiB
subtask5 0/50
23 Futási hiba 222ms 523052 KiB
24 Futási hiba 203ms 523028 KiB
25 Futási hiba 216ms 523016 KiB
26 Futási hiba 202ms 523020 KiB
27 Futási hiba 211ms 523036 KiB
28 Futási hiba 224ms 523028 KiB
29 Futási hiba 250ms 523036 KiB
30 Futási hiba 225ms 523032 KiB
31 Futási hiba 268ms 522944 KiB