Submission #1119027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119027		andrei_iorgulescu	Paths (RMI21_paths)	C++14	36 / 100	1042 ms	904 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n, k;
vector<pair<int, int>> g[2005];
int a[2005];
int t[2005];
int dp[2005];
vector<int> f[2005];

void dfs(int nod)
{
    for (auto vecin : g[nod])
    {
        if (t[nod] != vecin.first)
        {
            f[nod].push_back(vecin.first);
            a[vecin.first] = vecin.second;
            t[vecin.first] = nod;
            dfs(vecin.first);
        }
    }
}

void uf(int nod)
{
    for (auto fiu : f[nod])
    {
        dp[fiu] = a[fiu] + dp[nod];
        uf(fiu);
    }
}

int solve(int r)
{
    for (int i = 1; i <= n; i++)
        t[i] = 0, f[i].clear();
    a[r] = 0;
    dp[r] = 0;
    dfs(r);
    int ans = 0;
    for (int i = 1; i <= k; i++)
    {
        uf(r);
        int mx = 0, cn = r;
        for (int j = 1; j <= n; j++)
        {
            if (dp[j] > mx)
            {
                mx = dp[j];
                cn = j;
            }
        }
        ans += mx;
        while (cn != r)
            a[cn] = 0, cn = t[cn];
        if (mx == 0)
            break;
    }
    return ans;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> k;
    for (int i = 1; i < n; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        g[x].push_back({y, z});
        g[y].push_back({x, z});
    }
    for (int i = 1; i <= n; i++)
        cout << solve(i) << '\n';
    return 0;
}

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