89822024-02-09 21:55:28Vkrisztian01Testvérvárosokcpp17Futási hiba 0/100268ms524692 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1956 KiB
2Futási hiba218ms524692 KiB
subtask20/15
3Futási hiba4ms2804 KiB
4Hibás válasz3ms2908 KiB
5Futási hiba4ms3520 KiB
6Futási hiba3ms3116 KiB
7Futási hiba3ms3136 KiB
8Futási hiba263ms523832 KiB
9Futási hiba194ms523784 KiB
subtask30/15
10Futási hiba219ms523744 KiB
11Hibás válasz4ms3600 KiB
12Futási hiba222ms523484 KiB
13Hibás válasz17ms8516 KiB
14Futási hiba226ms523192 KiB
subtask40/20
15Futási hiba4ms4044 KiB
16Futási hiba204ms523188 KiB
17Futási hiba189ms523080 KiB
18Futási hiba197ms523040 KiB
19Futási hiba200ms523068 KiB
20Futási hiba202ms523064 KiB
21Futási hiba202ms523064 KiB
22Futási hiba204ms523060 KiB
subtask50/50
23Futási hiba222ms523052 KiB
24Futási hiba203ms523028 KiB
25Futási hiba216ms523016 KiB
26Futási hiba202ms523020 KiB
27Futási hiba211ms523036 KiB
28Futási hiba224ms523028 KiB
29Futási hiba250ms523036 KiB
30Futási hiba225ms523032 KiB
31Futási hiba268ms522944 KiB