oj.uz

Submission #855919

# Submission time Handle Problem Language Result Execution time Memory
855919 2023-10-02T09:19:13 Z lolismek Paths (RMI21_paths) C++14
0 / 100
 1 ms 604 KB 
#include <iostream>
#include <vector>

#define pii pair <int, int>

using namespace std;

const int NMAX = 2000;

vector <pii> adj[NMAX + 1];

int edg[NMAX + 1];
int par[NMAX + 1];
int lin[NMAX + 1];
int v[NMAX + 1];
pii tm[NMAX + 1];

int dfsTime;
void dfs(int node, int parent){
    par[node] = parent;
    lin[++dfsTime] = node;
    tm[node].first = dfsTime;

    for(pii child : adj[node]){
        if(child.first != parent){
            edg[child.first] = child.second;
            v[child.first] = v[node] + child.second;
            dfs(child.first, node);
        }
    }

    tm[node].second = dfsTime;
}

namespace AINT{
    pii aint[4 * NMAX + 1];
    int lazy[4 * NMAX + 1];

    void build(int node, int left, int right){
        lazy[node] = 0;
        if(left == right){
            aint[node] = {v[lin[left]], left};
            return;
        }

        int mid = (left + right) / 2;
        build(2 * node, left, mid);
        build(2 * node + 1, mid + 1, right);

        aint[node] = max(aint[2 * node], aint[2 * node + 1]);
    }

    void propag(int node, int left, int right){
        aint[node].first += lazy[node];
        if(left < right){
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }
        lazy[node] = 0;
    }

    void update(int node, int left, int right, int uleft, int uright, int val){
        propag(node, left, right);

        if(uleft <= left && right <= uright){
            lazy[node] += val;
            propag(node, left, right);
            return;
        }

        int mid = (left + right) / 2;
        if(uleft <= mid){
            update(2 * node, left, mid, uleft, uright, val);
        }
        if(mid + 1 <= uright){
            update(2 * node + 1, mid + 1, right, uleft, uright, val);
        }

        propag(2 * node, left, mid);
        propag(2 * node + 1, mid + 1, right);
        aint[node] = max(aint[2 * node], aint[2 * node + 1]);
    }

    pii query(int node, int left, int right, int qleft, int qright){
        propag(node, left, right);

        if(qleft <= left && right <= qright){
            return aint[node];
        }

        int mid = (left + right) / 2;
        pii ans = {0, 0};

        if(qleft <= mid){
            ans = query(2 * node, left, mid, qleft, qright);
        }
        if(mid + 1 <= qright){
            ans = max(ans, query(2 * node + 1, mid + 1, right, qleft, qright));
        }

        return ans;
    }
}

bool used[NMAX + 1];

int n, k;
int solve(int root){
    for(int i = 1; i <= n; i++){
        used[i] = false;
        v[i] = lin[i] = par[i] = edg[i] = 0;
        tm[i].first = tm[i].second = 0;
    }

    dfsTime = 0;
    edg[root] = 0;
    dfs(root, 0);

    AINT::build(1, 1, n);

    int ans = 0;
    for(int i = 1; i <= k; i++){
        pii x = AINT::query(1, 1, n, 1, n);
        int node = x.second;
        ans += x.first;
        while(node != 0 && !used[node]){
            used[node] = true;
            AINT::update(1, 1, n, tm[node].first, tm[node].second, -edg[node]);
            node = par[node];
        }
    }

    return ans;
}

int main(){

    cin >> n >> k;

    for(int i = 1; i <= n - 1; i++){
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }

    for(int i = 2; i <= 2; i++){
        cout << solve(i) << '\n';
    }

    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -