162792025-04-20 09:44:18HoraTestvérvárosokcpp17Hibás válasz 15/1001.108s262144 KiB
#include <bits/stdc++.h>
using namespace std;

vector<vector<array<long long, 2>>> g;
long long n, k, ans = 0;
vector<vector<long long>> a;

void dfs(long long v, long long p){
    a[v][0] = 1;
    for(auto [x, w] : g[v]){
        if(x == p) continue;
        dfs(x, v);
        for(long long i = 0; i < k; i++){
            ans += a[x][(i + w) % k] * a[v][i];
        }
        for(long long i = 0; i < k; i++){
            a[v][(i + w) % k] += a[x][i];
        }
    }
}

int main() {
    cin >> n >> k;
    g.resize(n + 1);
    a.resize(n + 1, vector<long long>(k, 0));
    for(long long i = 0; i < n - 1; i++){
        long long b, c, d;
        cin >> b >> c >> d;
        g[b].push_back({c, d % k});
        g[c].push_back({b, d % k});
    }
    dfs(1, 0);
    cout << ans << "\n";
    /*for(auto x : a){
        for(auto y : x) cout << y << " ";
        cout << "\n";
    }*/
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Hibás válasz1ms316 KiB
subtask20/15
3Elfogadva2ms564 KiB
4Elfogadva1ms316 KiB
5Hibás válasz4ms1108 KiB
6Hibás válasz23ms5520 KiB
7Elfogadva2ms316 KiB
8Hibás válasz14ms3724 KiB
9Hibás válasz4ms1332 KiB
subtask315/15
10Elfogadva17ms2100 KiB
11Elfogadva4ms820 KiB
12Elfogadva71ms6708 KiB
13Elfogadva63ms6196 KiB
14Elfogadva71ms6780 KiB
subtask40/20
15Hibás válasz6ms1588 KiB
16Hibás válasz35ms7996 KiB
17Hibás válasz100ms23092 KiB
18Hibás válasz398ms87604 KiB
19Hibás válasz270ms60168 KiB
20Hibás válasz245ms49972 KiB
21Elfogadva54ms8756 KiB
22Futási hiba193ms262144 KiB
subtask50/50
23Hibás válasz1.108s253248 KiB
24Hibás válasz651ms149144 KiB
25Hibás válasz689ms148168 KiB
26Hibás válasz273ms60980 KiB
27Hibás válasz465ms99892 KiB
28Hibás válasz393ms80692 KiB
29Futási hiba233ms262144 KiB
30Elfogadva71ms6452 KiB
31Futási hiba238ms262144 KiB