10575 | 2024-04-05 19:53:38 | 111 | Branch Cutting | cpp17 | Futási hiba 0/100 | 2.078s | 523688 KiB |
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_multiset=tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
#define int long long
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N,K1,K2;
cin>>N>>K1>>K2;
vector<vector<int>>g(N+1);
for(int i=0;i<N-1;i++){
int a,b;
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
int ans=0;
auto dfs=[&](auto self,int i,int p,int d)->ordered_multiset<int>{
ordered_multiset<int>s;
s.insert(d);
for(int j:g[i]){
if(j==p){
continue;
}
auto z=self(self,j,i,d+1);
if(s.size()<z.size()){
swap(s,z);
}
for(int x:z){
ans+=s.order_of_key(K2+d*2-x+1)-s.order_of_key(K1+d*2-x);
}
for(int x:z){
s.insert(x);
}
}
return s;
};
dfs(dfs,1,0,0);
cout<<ans<<'\n';
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Futási hiba | 3ms | 2256 KiB | ||||
2 | Hibás válasz | 3ms | 2216 KiB | ||||
subtask2 | 0/8 | ||||||
3 | Futási hiba | 3ms | 2400 KiB | ||||
4 | Hibás válasz | 3ms | 2700 KiB | ||||
5 | Futási hiba | 3ms | 2856 KiB | ||||
6 | Futási hiba | 3ms | 3220 KiB | ||||
7 | Futási hiba | 3ms | 3228 KiB | ||||
8 | Futási hiba | 3ms | 2996 KiB | ||||
9 | Futási hiba | 3ms | 3248 KiB | ||||
10 | Futási hiba | 3ms | 3192 KiB | ||||
11 | Futási hiba | 3ms | 3192 KiB | ||||
subtask3 | 0/15 | ||||||
12 | Futási hiba | 263ms | 523688 KiB | ||||
13 | Futási hiba | 264ms | 523656 KiB | ||||
14 | Futási hiba | 272ms | 523544 KiB | ||||
15 | Futási hiba | 305ms | 523324 KiB | ||||
16 | Futási hiba | 259ms | 523176 KiB | ||||
17 | Időlimit túllépés | 2.078s | 27460 KiB | ||||
18 | Időlimit túllépés | 2.066s | 29672 KiB | ||||
subtask4 | 0/10 | ||||||
19 | Futási hiba | 3ms | 3864 KiB | ||||
20 | Hibás válasz | 13ms | 3988 KiB | ||||
21 | Futási hiba | 3ms | 4012 KiB | ||||
22 | Futási hiba | 3ms | 4120 KiB | ||||
23 | Futási hiba | 3ms | 4352 KiB | ||||
24 | Futási hiba | 3ms | 4444 KiB | ||||
25 | Futási hiba | 3ms | 4320 KiB | ||||
26 | Futási hiba | 3ms | 4480 KiB | ||||
subtask5 | 0/25 | ||||||
27 | Futási hiba | 3ms | 4760 KiB | ||||
28 | Hibás válasz | 601ms | 6760 KiB | ||||
29 | Futási hiba | 3ms | 4856 KiB | ||||
30 | Futási hiba | 3ms | 4808 KiB | ||||
31 | Futási hiba | 3ms | 4700 KiB | ||||
32 | Futási hiba | 3ms | 4720 KiB | ||||
33 | Futási hiba | 3ms | 4868 KiB | ||||
34 | Futási hiba | 3ms | 5156 KiB | ||||
subtask6 | 0/42 | ||||||
35 | Futási hiba | 6ms | 14188 KiB | ||||
36 | Időlimit túllépés | 2.078s | 12904 KiB | ||||
37 | Futási hiba | 6ms | 13872 KiB | ||||
38 | Futási hiba | 7ms | 14100 KiB | ||||
39 | Futási hiba | 7ms | 14332 KiB | ||||
40 | Futási hiba | 7ms | 14292 KiB | ||||
41 | Futási hiba | 7ms | 14208 KiB | ||||
42 | Futási hiba | 7ms | 14208 KiB | ||||
43 | Futási hiba | 7ms | 14208 KiB |