Submission #848423

#	Time	Username	Problem	Language	Result	Execution time	Memory
848423		TahirAliyev	Paths (RMI21_paths)	C++17	0 / 100	1 ms	604 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long int
#define oo 1e9
#define pii pair<ll, int>

const int MAX = 2002;
int n, k;

pii segTree[4 * MAX];
int lazy[4 * MAX];

vector<pii> g[MAX];
int timeIn[MAX], timeOut[MAX], rtimeIn[MAX];
ll pathVal[MAX];
bool marked[MAX];
pii par[MAX];

void relax(int node, int l, int r){
    if(lazy[node] == 0) return;
    segTree[node].first += lazy[node];
    if(l != r){
        lazy[2 * node] += lazy[node];
        lazy[2 * node + 1] += lazy[node];
    }
    lazy[node] = 0;
}

void build(int node, int l, int r){
    if(l == r){
        segTree[node] = {pathVal[rtimeIn[l]], rtimeIn[l]};
        return;
    }
    int mid = (l + r) / 2;
    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);
    segTree[node] = max(segTree[2 * node], segTree[2 * node + 1]);
}

void update(int node, int l, int r, int ul, int ur, ll val){
    relax(node, l, r);
    if(ul > r || l > ur) return;
    if(ul <= l && r <= ur){
        lazy[node] += val;
        relax(node, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update(2 * node, l, mid, ul, ur, val);
    update(2 * node + 1, mid + 1, r, ul, ur, val);
    segTree[node] = max(segTree[2 * node], segTree[2 * node + 1]);
}

int t = 0;
void dfs(int node, int p, int h){
    timeIn[node] = ++t;
    rtimeIn[t] = node;
    pathVal[node] = h;
    for(pii to : g[node]){
        if(p == to.first) continue;
        par[to.first] = make_pair(node, to.second);
        dfs(to.first, node, h + to.second);
    }
    timeOut[node] = t;
}

int main(){
    cin >> n >> k;
    for(int i = 1; i < n; i++){
        int u, v, a; cin >> u >> v >> a;
        g[u].push_back({v, a});
        g[v].push_back({u, a});
    }
    for(int i = 1; i <= n; i++){
        t = 0;
        memset(segTree, 0, sizeof(segTree));
        memset(lazy, 0, sizeof(lazy));
        memset(marked, 0, sizeof(marked));

        dfs(i, i, 0);
        build(1, 1, n);
        ll ans = 0;
        for(int j = 0; j < k; j++){
            pii m = segTree[1];
            if(m.first == 0) break;
            ans += m.first;
            int a = m.second;
            while(a != i){
                if(marked[a]) break;
                update(1, 1, n, timeIn[a], timeOut[a], -par[a].second);
                marked[a] = true;
                a = par[a].first;
            }
        }
        cout << ans << '\n';
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:79:43: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<long long int, int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
   79 |         memset(segTree, 0, sizeof(segTree));
      |                                           ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from Main.cpp:2:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, int>' declared here
  211 |     struct pair
      |            ^~~~

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