Submission #643563

#	Time	Username	Problem	Language	Result	Execution time	Memory
643563		danikoynov	Paths (RMI21_paths)	C++14	56 / 100	1078 ms	12096 KiB

Main

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
const int maxn = 1e5 + 10;

int n, k;
ll depth[maxn], mx_depth[maxn], num[maxn];
vector < pair < int, ll > > g[maxn];

void calc(int ver, int par)
{
    mx_depth[ver] = depth[ver];
    for (pair < int, ll > nb : g[ver])
    {
        if (nb.first == par)
            continue;
        depth[nb.first] = depth[ver] + nb.second;
        calc(nb.first, ver);
        mx_depth[ver] = max(mx_depth[ver], mx_depth[nb.first]);
    }
}

bool cmp(pair < int, ll > p1, pair < int, ll > p2)
{
    return mx_depth[p1.first] > mx_depth[p2.first];
}

void trav(int ver, int par, ll cur_depth)
{
    sort(g[ver].begin(), g[ver].end(), cmp);
    ///cout << ver << " " << par << " " << cur_depth << endl;
    bool leaf = true, tf = true;
    for (pair < int, ll > nb : g[ver])
    {
        if (nb.first == par)
            continue;
        leaf = false;
        if (tf)
        {
            tf = false;
            trav(nb.first, ver, cur_depth + nb.second);
        }
        else
        trav(nb.first, ver, nb.second);
    }

    if (leaf)
        num[ver] = cur_depth;
}

void solve()
{
    cin >> n >> k;
    for (int i = 1; i < n; i ++)
    {
        int v, u;
        ll l;
        cin >> v >> u >> l;
        g[v].push_back({u, l});
        g[u].push_back({v, l});
    }

    for (int root = 1; root <= n; root ++)
    {
        depth[root] = 0;
        for (int i = 1; i <= n; i ++)
            num[i] = 0;
        calc(root, - 1);
        trav(root, -1, 0);
        /**for (int i = 1; i <= n; i ++)
            cout << num[i] << " ";
        cout << endl;*/
        sort(num + 1, num + n + 1);
        ll ans = 0;
        for (int i = n; i > n - k; i --)
            ans = ans + num[i];
        cout << ans << endl;
    }


}

int main()
{
    solve();
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32