oj.uz

Submission #439842

# Submission time Handle Problem Language Result Execution time Memory
439842 2021-07-01T01:28:55 Z 반딧불(#7618) Road Closures (APIO21_roads) C++17
22 / 100
 1048 ms 417324 KB 
#include <bits/stdc++.h>
#include "roads.h"

using namespace std;

typedef long long ll;

struct Edge{
    int u, v; ll w;
    Edge(){}
    Edge(int u, int v, ll w): u(u), v(v), w(w){}
};

struct segTree{
    struct Node{
        Node *l, *r;
        ll s, e;
        ll sum, cnt;

        Node(ll s, ll e): s(s), e(e){
            l = r = nullptr;
            sum = cnt = 0;
        }

        ~Node(){
            if(l) delete l;
            if(r) delete r;
        }

        void addValue(ll x, ll w){
            if(s==e){
                sum += x*w;
                cnt += w;
                return;
            }
            ll m = (s+e)>>1;
            if(x <= m){
                if(!l) l = new Node(s, m);
                l->addValue(x, w);
            }
            else{
                if(!r) r = new Node(m+1, e);
                r->addValue(x, w);
            }
            sum = (l ? l->sum : 0LL) + (r ? r->sum : 0LL);
            cnt = (l ? l->cnt : 0LL) + (r ? r->cnt : 0LL);
        }

        ll kthSum(ll k){
            if(!k) return 0;
            if(cnt <= k) return sum;
            if(s==e) return k * s;
            if(r && r->cnt >= k) return r->kthSum(k);
            return (r ? r->sum : 0) + l->kthSum(k - (r?r->cnt:0));
        }
    } *root;
    ll defVal;

    segTree(){
        root = new Node(0, 1e18);
        defVal = 0;
    }

    void quit(){
        if(root) delete root;
    }

    void addValue(ll x){
        root->addValue(x, 1);
    }
    void delValue(ll x){
        root->addValue(x, -1);
    }

    ll kthSum(ll k){
        return defVal - root->kthSum(k);
    }
} tree[100002];

int n, k;
vector<pair<int, ll> > link[100002];
vector<Edge> edgeList;
int deg[100002];
ll DP[100002][2];

int visited[100002];
vector<ll> ans;

void dfs(int x, int par = -1){
    vector<pair<ll, ll> > vec;
    visited[x] = k;

    for(auto y: link[x]){
        if(y.first == par) continue;
        dfs(y.first, x);
        vec.push_back(make_pair(DP[y.first][0] + y.second, DP[y.first][1]));
    }
    for(auto p: vec){
        tree[x].defVal += p.first;
        tree[x].addValue(p.first - p.second);
    }

    DP[x][0] = tree[x].kthSum(k);
    DP[x][1] = tree[x].kthSum(k-1);

    for(auto p: vec){
        tree[x].defVal -= p.first;
        tree[x].delValue(p.first - p.second);
    }
}

vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
    n = N;
    ans.resize(n);
    for(int i=0; i<n-1; i++){
        deg[U[i]]++, deg[V[i]]++;
        edgeList.push_back(Edge(U[i], V[i], W[i]));
        ans[0] += W[i];
    }

    vector<pair<int, int> > degList;
    for(int i=0; i<n; i++){
        visited[i] = -1;
        degList.push_back(make_pair(deg[i], i));
    }
    sort(degList.rbegin(), degList.rend());
    sort(edgeList.begin(), edgeList.end(), [&](Edge &a, Edge &b){
        return min(deg[a.u], deg[a.v]) > min(deg[b.u], deg[b.v]);
    });

    for(int idx=1; idx<degList[0].first; idx++){
        k = idx;
        while(!degList.empty() && degList.back().first < idx){
            int x = degList.back().second;
            for(auto y: link[x]){
                tree[y.first].defVal += y.second;
                tree[y.first].addValue(y.second);
            }
            degList.pop_back();
        }
        if(degList.empty()) break;

        while(!edgeList.empty()){
            if(deg[edgeList.back().u] < idx || deg[edgeList.back().v] < idx) edgeList.pop_back();
            else break;
        }
        for(auto p: degList) link[p.second].clear();
        for(auto e: edgeList){
            link[e.u].push_back(make_pair(e.v, e.w));
            link[e.v].push_back(make_pair(e.u, e.w));
        }

        for(auto p: degList){
            if(visited[p.second] != k){
                dfs(p.second);
                ans[idx] += DP[p.second][0];
            }
        }
    }

    for(int i=0; i<n; i++) tree[i].quit();
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10444 KB Output is correct
2 Correct 18 ms 13016 KB Output is correct
3 Correct 19 ms 13132 KB Output is correct
4 Correct 13 ms 10748 KB Output is correct
5 Correct 12 ms 10700 KB Output is correct
6 Correct 13 ms 10700 KB Output is correct
7 Correct 11 ms 10444 KB Output is correct
8 Correct 13 ms 10764 KB Output is correct
9 Correct 13 ms 10800 KB Output is correct
10 Correct 9 ms 10444 KB Output is correct
11 Correct 9 ms 10480 KB Output is correct
12 Correct 145 ms 19488 KB Output is correct
13 Correct 256 ms 26980 KB Output is correct
14 Correct 722 ms 100304 KB Output is correct
15 Correct 880 ms 115428 KB Output is correct
16 Correct 781 ms 113236 KB Output is correct
17 Correct 248 ms 27848 KB Output is correct
18 Correct 8 ms 10480 KB Output is correct
19 Correct 214 ms 26224 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10444 KB Output is correct
2 Incorrect 658 ms 346572 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10444 KB Output is correct
2 Correct 9 ms 10444 KB Output is correct
3 Correct 9 ms 10444 KB Output is correct
4 Incorrect 10 ms 11200 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10444 KB Output is correct
2 Correct 9 ms 10444 KB Output is correct
3 Correct 9 ms 10444 KB Output is correct
4 Incorrect 10 ms 11200 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1048 ms 254008 KB Output is correct
2 Correct 1043 ms 249712 KB Output is correct
3 Correct 358 ms 25300 KB Output is correct
4 Correct 1041 ms 263776 KB Output is correct
5 Correct 396 ms 25192 KB Output is correct
6 Correct 329 ms 23412 KB Output is correct
7 Correct 763 ms 166200 KB Output is correct
8 Correct 219 ms 26804 KB Output is correct
9 Correct 658 ms 204284 KB Output is correct
10 Correct 891 ms 208556 KB Output is correct
11 Correct 348 ms 26856 KB Output is correct
12 Correct 269 ms 26296 KB Output is correct
13 Correct 8 ms 10444 KB Output is correct
14 Correct 691 ms 377036 KB Output is correct
15 Correct 738 ms 417324 KB Output is correct
16 Correct 22 ms 15348 KB Output is correct
17 Correct 23 ms 15400 KB Output is correct
18 Correct 18 ms 11000 KB Output is correct
19 Correct 13 ms 10724 KB Output is correct
20 Correct 15 ms 10828 KB Output is correct
21 Correct 227 ms 26292 KB Output is correct

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1048 ms 254008 KB Output is correct
2 Correct 1043 ms 249712 KB Output is correct
3 Correct 358 ms 25300 KB Output is correct
4 Correct 1041 ms 263776 KB Output is correct
5 Correct 396 ms 25192 KB Output is correct
6 Correct 329 ms 23412 KB Output is correct
7 Correct 763 ms 166200 KB Output is correct
8 Correct 219 ms 26804 KB Output is correct
9 Correct 658 ms 204284 KB Output is correct
10 Correct 891 ms 208556 KB Output is correct
11 Correct 348 ms 26856 KB Output is correct
12 Correct 269 ms 26296 KB Output is correct
13 Correct 8 ms 10444 KB Output is correct
14 Correct 691 ms 377036 KB Output is correct
15 Correct 738 ms 417324 KB Output is correct
16 Correct 22 ms 15348 KB Output is correct
17 Correct 23 ms 15400 KB Output is correct
18 Correct 18 ms 11000 KB Output is correct
19 Correct 13 ms 10724 KB Output is correct
20 Correct 15 ms 10828 KB Output is correct
21 Correct 227 ms 26292 KB Output is correct
22 Correct 9 ms 10364 KB Output is correct
23 Correct 13 ms 10448 KB Output is correct
24 Correct 9 ms 10444 KB Output is correct
25 Incorrect 978 ms 241836 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10444 KB Output is correct
2 Correct 18 ms 13016 KB Output is correct
3 Correct 19 ms 13132 KB Output is correct
4 Correct 13 ms 10748 KB Output is correct
5 Correct 12 ms 10700 KB Output is correct
6 Correct 13 ms 10700 KB Output is correct
7 Correct 11 ms 10444 KB Output is correct
8 Correct 13 ms 10764 KB Output is correct
9 Correct 13 ms 10800 KB Output is correct
10 Correct 9 ms 10444 KB Output is correct
11 Correct 9 ms 10480 KB Output is correct
12 Correct 145 ms 19488 KB Output is correct
13 Correct 256 ms 26980 KB Output is correct
14 Correct 722 ms 100304 KB Output is correct
15 Correct 880 ms 115428 KB Output is correct
16 Correct 781 ms 113236 KB Output is correct
17 Correct 248 ms 27848 KB Output is correct
18 Correct 8 ms 10480 KB Output is correct
19 Correct 214 ms 26224 KB Output is correct
20 Correct 8 ms 10444 KB Output is correct
21 Incorrect 658 ms 346572 KB Output isn't correct
22 Halted 0 ms 0 KB -