10204 2024. 03. 29 13:36:20 111 Testvérvárosok cpp17 Hibás válasz 20/100 75ms 38856 KiB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,K;
	cin>>N>>K;
	vector<vector<pair<int,int>>>g(N+1);
	for(int i=0;i<N-1;i++){
		int a,b,d;
		cin>>a>>b>>d;
		g[a].emplace_back(b,d);
		g[b].emplace_back(a,d);
	}
	int ans=0;
	auto dfs=[&](auto self,int i,int p,int x)->map<int,int>{
		map<int,int>s;
		for(auto[j,d]:g[i]){
			if(j==p){
				continue;
			}
			auto z=self(self,j,i,x+d);
			int q=x%K;
			ans+=z.count(q)?z[q]:0;
			if(z.size()>s.size()){
				swap(s,z);
			}
			for(auto[y,c]:z){
				int q=((x*2-y)%K+K)%K;
				ans+=s.count(q)?s[q]:0;
			}
			for(auto[y,c]:z){
				s[y]+=c;
			}
		}
		s[x%K]++;
		return s;
	};
	dfs(dfs,1,0,0);
	cout<<ans<<'\n';
	return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1828 KiB
2 Elfogadva 3ms 2068 KiB
subtask2 0/15
3 Elfogadva 3ms 2288 KiB
4 Elfogadva 3ms 2320 KiB
5 Hibás válasz 3ms 2656 KiB
6 Hibás válasz 3ms 2768 KiB
7 Hibás válasz 3ms 2876 KiB
8 Elfogadva 3ms 2904 KiB
9 Hibás válasz 3ms 3060 KiB
subtask3 0/15
10 Hibás válasz 10ms 4768 KiB
11 Elfogadva 4ms 4860 KiB
12 Hibás válasz 37ms 10388 KiB
13 Hibás válasz 32ms 10096 KiB
14 Hibás válasz 37ms 10824 KiB
subtask4 20/20
15 Elfogadva 3ms 3504 KiB
16 Elfogadva 3ms 4256 KiB
17 Elfogadva 8ms 7900 KiB
18 Elfogadva 25ms 19668 KiB
19 Elfogadva 30ms 26248 KiB
20 Elfogadva 39ms 35088 KiB
21 Elfogadva 30ms 32636 KiB
22 Elfogadva 52ms 38856 KiB
subtask5 0/50
23 Hibás válasz 68ms 12208 KiB
24 Hibás válasz 39ms 8880 KiB
25 Hibás válasz 48ms 9524 KiB
26 Hibás válasz 19ms 5828 KiB
27 Hibás válasz 37ms 8880 KiB
28 Hibás válasz 64ms 12060 KiB
29 Hibás válasz 71ms 11780 KiB
30 Hibás válasz 32ms 11460 KiB
31 Hibás válasz 75ms 12924 KiB