5301 2023. 04. 25 17:33:10 gortomi Testvérvárosok cpp17 Hibás válasz 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1892 KiB
2 Hibás válasz 3ms 2128 KiB
subtask2 0/15
3 Hibás válasz 3ms 2336 KiB
4 Elfogadva 3ms 2552 KiB
5 Hibás válasz 4ms 2912 KiB
6 Hibás válasz 4ms 3128 KiB
7 Hibás válasz 4ms 3208 KiB
8 Elfogadva 3ms 3156 KiB
9 Hibás válasz 6ms 3512 KiB
subtask3 0/15
10 Hibás válasz 187ms 5156 KiB
11 Elfogadva 301ms 4384 KiB
12 Hibás válasz 1.133s 10488 KiB
13 Hibás válasz 1.449s 9832 KiB
14 Hibás válasz 1.32s 10364 KiB
subtask4 0/20
15 Elfogadva 4ms 4096 KiB
16 Elfogadva 29ms 4176 KiB
17 Elfogadva 1.125s 5764 KiB
18 Időlimit túllépés 1.575s 6460 KiB
19 Időlimit túllépés 1.572s 7884 KiB
20 Időlimit túllépés 1.557s 9800 KiB
21 Időlimit túllépés 1.572s 9552 KiB
22 Időlimit túllépés 1.569s 10704 KiB
subtask5 0/50
23 Időlimit túllépés 1.569s 6808 KiB
24 Hibás válasz 628ms 7956 KiB
25 Hibás válasz 800ms 9056 KiB
26 Hibás válasz 12ms 5868 KiB
27 Hibás válasz 644ms 7956 KiB
28 Hibás válasz 1.144s 11200 KiB
29 Hibás válasz 949ms 10944 KiB
30 Hibás válasz 1.228s 10888 KiB
31 Hibás válasz 1.294s 11564 KiB