5301 2023. 04. 25 17:33:10 gortomi Testvérvárosok cpp17 Wrong answer 0/100 1.575s 11564 KiB 
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int, int> > > g;
vector<int> d, s, act, to, dep;
long long ans = 0;
int k, c;
vector<bool> w;
void dfs(int n, int p)
{
    s[n] = 1;
    for(auto x : g[n])
    {
        int y = x.first;
        if(y != p && !w[y])
        {
            dfs(y, n);
            s[n] += s[y];
        }
    }
}
int fc(int n, int p)
{
    for(auto x : g[n])
    {
        int y = x.first;
        if(!w[y] && y != p)
        {
            if(s[y] > c / 2) return fc(y, n);
        }
    }
    return n;
}
void add(int n, int p)
{
    ans += dep[(k - d[n]) % k];
    for(auto x : g[n])
    {
        int y = x.first;
        if(!w[y] && y != p)
        {
            d[y] = (d[n] + x.second) % k;
            add(y, n);
        }
    }
}
void solve(int n)
{
    w[n] = 1;
    c = s[n];
    dfs(n, 0);
    int u = fc(n, 0);
    dep[0]++;
    to.clear();
    for(auto x : g[n])
    {
        int y = x.first;
        if(!w[y])
        {
            act.clear();
            d[y] = x.second % k;
            add(y, n);
            for(auto x : act)
            {
                dep[d[x]]++;
            }
        }
    }
    for(auto x : to) dep[d[x]]--;
    dep[0]--;
    for(auto x : g[n])
    {
        int y = x.first;
        if(!w[y]) solve(y);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n >> k;
    g.resize(n + 1);
    d.resize(n + 1);
    w.resize(n + 1);
    s.resize(n + 1);
    dep.resize(k);
    for(int i = 0; i < n - 1; i++)
    {
        int x, y, w;
        cin >> x >> y >> w;
        g[x].push_back({y, w});
        g[y].push_back({x, w});
    }
    solve(1);
    cout << ans;
}
Subtask Sum Test Verdict Time Memory
subtask1 0/0
1 Accepted 3ms 1892 KiB
2 Wrong answer 3ms 2128 KiB
subtask2 0/15
3 Wrong answer 3ms 2336 KiB
4 Accepted 3ms 2552 KiB
5 Wrong answer 4ms 2912 KiB
6 Wrong answer 4ms 3128 KiB
7 Wrong answer 4ms 3208 KiB
8 Accepted 3ms 3156 KiB
9 Wrong answer 6ms 3512 KiB
subtask3 0/15
10 Wrong answer 187ms 5156 KiB
11 Accepted 301ms 4384 KiB
12 Wrong answer 1.133s 10488 KiB
13 Wrong answer 1.449s 9832 KiB
14 Wrong answer 1.32s 10364 KiB
subtask4 0/20
15 Accepted 4ms 4096 KiB
16 Accepted 29ms 4176 KiB
17 Accepted 1.125s 5764 KiB
18 Time limit exceeded 1.575s 6460 KiB
19 Time limit exceeded 1.572s 7884 KiB
20 Time limit exceeded 1.557s 9800 KiB
21 Time limit exceeded 1.572s 9552 KiB
22 Time limit exceeded 1.569s 10704 KiB
subtask5 0/50
23 Time limit exceeded 1.569s 6808 KiB
24 Wrong answer 628ms 7956 KiB
25 Wrong answer 800ms 9056 KiB
26 Wrong answer 12ms 5868 KiB
27 Wrong answer 644ms 7956 KiB
28 Wrong answer 1.144s 11200 KiB
29 Wrong answer 949ms 10944 KiB
30 Wrong answer 1.228s 10888 KiB
31 Wrong answer 1.294s 11564 KiB