Submission #848493

#	Time	Username	Problem	Language	Result	Execution time	Memory
848493		TahirAliyev	Paths (RMI21_paths)	C++17	36 / 100	637 ms	1088 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];
ll lazy[4 * MAX];

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

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

void build(int node, int l, int r){
    if(l == r){
        segTree[node] = {pathVal[leafs[l]], leafs[l]};
        return;
    }
    int mid = (l + r) >> 1;
    build(node << 1, l, mid);
    build(node << 1 | 1, mid + 1, r);
    segTree[node] = max(segTree[node << 1], segTree[node << 1| 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) >> 1;
    update(node << 1, l, mid, ul, ur, val);
    update(node << 1 | 1, mid + 1, r, ul, ur, val);
    segTree[node] = max(segTree[node << 1], segTree[node << 1 | 1]);
}


int t = 1;
void dfs(int node, int p, ll h){
    timeIn[node] = t;
    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 - 1;
    if(g[node].size() == 1 && node != p){
        leafs.push_back(node);
        timeOut[node] = t++;
    }
}

int main(){
    scanf("%d%d", &n, &k);
    for(int i = 1; i < n; i++){
        int u, v, a; scanf("%d%d%d", &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(lazy, 0, sizeof(lazy));
        memset(marked, 0, sizeof(marked));
        leafs.clear();

        dfs(i, i, 0);
        build(1, 0, t - 1);
        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, 0, t - 1, 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:76:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     scanf("%d%d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:78:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         int u, v, a; scanf("%d%d%d", &u, &v, &a);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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