oj.uz

Submission #552209

# Submission time Handle Problem Language Result Execution time Memory
552209 2022-04-22T17:55:19 Z marsxiang5902 Road Closures (APIO21_roads) C++17
7 / 100
 83 ms 33580 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int MN = 1e5+5;

int N, sz[MN]; vector<pair<int,int>> adjl[MN]; ll ans[MN]; vector<ll> diffs[MN];
        
template <class T> void clr(T pq[]){
    while(!pq[1].empty() && pq[1].top() == pq[0].top()){
        pq[1].pop();
        pq[0].pop();
    }
}

struct KMin{
    priority_queue<ll> iq[2]; priority_queue<ll, vector<ll>, greater<ll>> oq[2];
    int k, infs, sz; ll curSum;
    void init(int _k){
        iq[0] = iq[1] = {};
        oq[0] = oq[1] = {};
        k = _k;
        sz = infs = 0;
        curSum = 0;
    }
    void insert(ll x){
        curSum += x;
        iq[0].push(x);
        if(++sz > k){
            clr(iq);
            ll rem = iq[0].top(); iq[0].pop();
            oq[0].push(rem);
            curSum -= rem;
        }
    }
    void erase(ll x){
        assert(sz--);
        if(clr(iq); iq[0].top() >= x){
            curSum -= x;
            iq[1].push(x);
            if(sz >= k){
                clr(oq);
                ll ins = oq[0].top(); oq[0].pop();
                iq[0].push(ins);
                curSum += ins;
            }
        } else oq[1].push(x);
    }
    void decK(){ insert(0); }
    ll query(){ return curSum; }
} kMin;

void dfs(int u, int pw){
    sort(adjl[u].begin(), adjl[u].end(), [](pair<int,int> lhs, pair<int,int> rhs){
        return sz[lhs.first] > sz[rhs.first];
    });
    for(auto [v, w]: adjl[u]){
        adjl[v].erase(find(adjl[v].begin(), adjl[v].end(), pair(u, w)));
        dfs(v, w);
    }
    diffs[u].resize(sz[u]);
    kMin.init(sz[u] - 1);
    for(auto [v, w]: adjl[u])
        kMin.insert(w);
    for(int k = 1; k < sz[u]; k++){
        for(auto [v, w]: adjl[u]){
            if(sz[v] <= k) break;
            kMin.erase(w);
            kMin.insert(w - diffs[v][k]);
            assert(w >= diffs[v][k]);
        }
        assert(kMin.k == sz[u] - k);
        ll res1 = kMin.query();
        kMin.decK();
        ll res2 = kMin.query();
        ans[k] += res1;
        diffs[u][k] = res1 - res2;
        ans[k] += min(0LL, pw - diffs[u][k]);
        diffs[u][k] = min(ll(pw), diffs[u][k]);
        for(auto [v, w]: adjl[u]){
            if(sz[v] <= k) break;
            kMin.insert(w);
            kMin.erase(w - diffs[v][k]);
        }
    }
}

vector<ll> minimum_closure_costs(int _N, vector<int> us, vector<int> vs, 
    vector<int> ws){
    N = _N;
    for(int i = 0, u, v, w; i < N-1; i++){
        u = us[i]; v = vs[i]; w = ws[i];
        adjl[u].emplace_back(v, w);
        adjl[v].emplace_back(u, w);
    }
    for(int i = 0; i < N; i++)
        sz[i] = adjl[i].size();
    ++sz[0];
    dfs(0, 0);
    ans[0] = accumulate(ws.begin(), ws.end(), 0LL);
    for(int k = 1; k < sz[0]; k++)
        ans[k] -= diffs[0][k];
    return vector<ll>(ans, ans+N);
}

#ifdef LOCAL_PROJECT
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    int N; cin >> N;
    vector<int> us(N-1), vs(N-1), ws(N-1);
    for(int i = 0; i < N-1; i++)
        cin >> us[i] >> vs[i] >> ws[i];
    vector<ll> ans = minimum_closure_costs(N, us, vs, ws);
    for(int i = 0; i < N; i++)
        printf("%d%c", ans[i], " \n"[i==N-1]);

    return 0;
}
#endif

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Runtime error 9 ms 10452 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 74 ms 28632 KB Output is correct
3 Correct 83 ms 31696 KB Output is correct
4 Correct 80 ms 33484 KB Output is correct
5 Correct 81 ms 33484 KB Output is correct
6 Correct 5 ms 5380 KB Output is correct
7 Correct 5 ms 5460 KB Output is correct
8 Correct 4 ms 5588 KB Output is correct
9 Correct 4 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 62 ms 22144 KB Output is correct
13 Correct 79 ms 33452 KB Output is correct
14 Correct 2 ms 4948 KB Output is correct
15 Correct 67 ms 30700 KB Output is correct
16 Correct 76 ms 33580 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Runtime error 7 ms 9948 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Runtime error 7 ms 9948 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 51 ms 22544 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 51 ms 22544 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Runtime error 9 ms 10452 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -