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 |