oj.uz

Submission #643213

# Submission time Handle Problem Language Result Execution time Memory
643213 2022-09-21T13:41:35 Z danikoynov Paths (RMI21_paths) C++14
19 / 100
 600 ms 17436 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 10 ms 4948 KB Output is correct
4 Correct 9 ms 4948 KB Output is correct
5 Correct 10 ms 4948 KB Output is correct
6 Correct 8 ms 4948 KB Output is correct
7 Correct 10 ms 4948 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 10 ms 4948 KB Output is correct
4 Correct 9 ms 4948 KB Output is correct
5 Correct 10 ms 4948 KB Output is correct
6 Correct 8 ms 4948 KB Output is correct
7 Correct 10 ms 4948 KB Output is correct
8 Execution timed out 1085 ms 5148 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 10 ms 4948 KB Output is correct
4 Correct 9 ms 4948 KB Output is correct
5 Correct 10 ms 4948 KB Output is correct
6 Correct 8 ms 4948 KB Output is correct
7 Correct 10 ms 4948 KB Output is correct
8 Execution timed out 1085 ms 5148 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 17436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 10 ms 4948 KB Output is correct
4 Correct 9 ms 4948 KB Output is correct
5 Correct 10 ms 4948 KB Output is correct
6 Correct 8 ms 4948 KB Output is correct
7 Correct 10 ms 4948 KB Output is correct
8 Execution timed out 1085 ms 5148 KB Time limit exceeded
9 Halted 0 ms 0 KB -