Submission #643369

#	Time	Username	Problem	Language	Result	Execution time	Memory
643369		danikoynov	Paths (RMI21_paths)	C++14	36 / 100	1091 ms	24956 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];

int timer, f[maxn], in[maxn], out[maxn];
void trav(int v, int p)
{
    par[v] = p;
    in[v] = ++ timer;
    f[timer] = v;
    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);
    }
    out[v] = timer;
}


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);
    }
}

pair < ll, int > tree[4 * maxn];
ll lazy[4 * maxn];

void build_tree(int root, int left, int right)
{
    lazy[root] = 0;
    if (left == right)
    {
        tree[root] = {depth[f[left]], f[left]};
        return;
    }

    int mid = (left + right) / 2;
    build_tree(root * 2, left, mid);
    build_tree(root * 2 + 1, mid + 1, right);

    tree[root] = max(tree[root * 2], tree[root * 2 + 1]);

}


void push_lazy(int root, int left, int right)
{
    ///cout << root << " ::: " << lazy[root] << endl;
    tree[root].first += lazy[root];

    if (left != right)
    {
        lazy[root * 2] += lazy[root];
        lazy[root * 2 + 1] += lazy[root];
    }

    lazy[root] = 0;
}

void update(int root, int left, int right, int qleft, int qright, ll val)
{


    push_lazy(root, left, right);
///cout << root << " " << left << " " << right << " " << qleft << " " << qright << " " << val << endl;
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        lazy[root] += val;
        push_lazy(root, left, right);
        return;
    }

    int mid = (left + right) / 2;
    update(root * 2, left, mid, qleft, qright, val);
    update(root * 2 + 1, mid + 1, right, qleft, qright, val);
    ///cout << root << " " << left << " " << right << " " << qleft << " " << qright << " " << val << endl;
    tree[root] = max(tree[root * 2], tree[root * 2 + 1]);
}

pair < ll, int > query(int root, int left, int right, int qleft, int qright)
{

    push_lazy(root, left, right);
///cout << root << " " << left << " " << right << " ::: " << tree[root].first << endl;
    if (left > qright || right < qleft)
        return {(ll)-1, -1};

    if (left >= qleft && right <= qright)
        return tree[root];

    int mid = (left + right) / 2;
    return max(query(root * 2, left, mid, qleft, qright),
               query(root * 2 + 1, mid + 1, right, qleft, qright));
}
int fver;
void clean(int v)
{
    while(!used[v])
    {
        ///cout << "rem " << v << " " << in[v] << " " << out[v] << endl;
        used[v] = 1;
        update(1, 1, n, in[v], out[v], - g[par[v]][rev_idx[v]].second);
        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;

        timer = 0;
        trav(ver, -1);
        /**for (int i = 1; i <= n; i ++)
            cout << f[i] << " ";
        cout << endl;*/
        depth[ver] = 0;
        calc(ver);
        build_tree(1, 1, n);
        ///update(1, 1, n, 2, 11, -2);
        ///cout << query(1, 1, n, 8, 8).first << endl;
        ///exit(0);
        ll ans = 0;
        used[ver] = 1;
        for (int i = 1; i <= k; i ++)
        {
            int mx = tree[1].second;
            ///cout << tree[1].first << " " << tree[1].second << " " << query(1, 1, n, 8, 8).first << endl;
            ans = ans + tree[1].first;
            clean(mx);
        }

        cout << ans << endl;
    }
}

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

Compilation message (stderr)

Main.cpp: In function 'void trav(int, int)':
Main.cpp:18: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]
   18 |     for (int i = 0; i < g[v].size(); i ++)
      |                     ~~^~~~~~~~~~~~~
Main.cpp: In function 'void calc(int)':
Main.cpp:32: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]
   32 |     for (int i = 0; i < g[v].size(); i++)
      |                     ~~^~~~~~~~~~~~~

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