Submission #643213

#	Time	Username	Problem	Language	Result	Execution time	Memory
643213		danikoynov	Paths (RMI21_paths)	C++14	19 / 100	1085 ms	17436 KiB

Main

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 10;

int n, k, par[maxn], used[maxn], rev_idx[maxn];
ll depth[maxn];
vector < pair < int, ll > > g[maxn], sg[maxn];

void trav(int v, int p)
{
    par[v] = p;
    for (int i = 0; i < g[v].size(); i ++)
    {
        pair < int, ll > nb = g[v][i];
        if (nb.first == p)
            continue;
        rev_idx[nb.first] = i;
        trav(nb.first, v);
    }
}


void calc(int v)
{
    for (int i = 0; i < g[v].size(); i++)
    {
        pair < int, ll > nb = g[v][i];
        if (nb.first == par[v])
            continue;
        depth[nb.first] = depth[v] + nb.second;
        calc(nb.first);
    }
}

int fver;
void clean(int v)
{
    while(!used[v])
    {
        used[v] = 1;
        g[par[v]][rev_idx[v]].second = 0;
        v = par[v];
    }
}

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});
        sg[v].push_back({u, l});
        g[u].push_back({v, l});
        sg[u].push_back({v, l});
    }

    for (int ver = 1; ver <= n; ver ++)
    {
fver = ver;
    for (int i = 1; i <= n; i ++)
        g[i] = sg[i], used[i] = 0;
    trav(ver, -1);

    ll ans = 0;
    used[ver] = 1;
    for (int i = 1; i <= k; i ++)
    {

    depth[ver] = 0;
        calc(ver);
        int mx = 1;
        for (int j = 2; j <= n; j ++)
            if (depth[j] > depth[mx])
            mx = j;
        ans = ans + depth[mx];

        clean(mx);
    }

    cout << ans << endl;
    }
}

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

Compilation message (stderr)

Main.cpp: In function 'void trav(int, int)':
Main.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for (int i = 0; i < g[v].size(); i ++)
      |                     ~~^~~~~~~~~~~~~
Main.cpp: In function 'void calc(int)':
Main.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int i = 0; i < g[v].size(); i++)
      |                     ~~^~~~~~~~~~~~~

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