oj.uz

Submission #416602

# Submission time Handle Problem Language Result Execution time Memory
416602 2021-06-02T16:54:32 Z doowey Road Closures (APIO21_roads) C++14
12 / 100
 311 ms 93468 KB 
#include <bits/stdc++.h>
#include "roads.h"

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pii;

#define fi first
#define se second
#define mp make_pair

const int N = (int)1e5 + 10;

vector<int> u, v, w;
int n;

vector<pii> T[N];

bool comp(pii i, pii j){
    return w[i.se] < w[j.se];
}

struct edge{
    int nex;
    int oo;
    int weight;
};



bool active[N];
vector<int> ad[N];

ll dp[N][2];

struct segment_tree{
    vector<pii> TREE;
    int sz;
    void init(int nn){
        sz = nn;
        TREE.resize(sz * 4 + 16);
    }
    void add(int node, int cl, int cr, int v, int cc, ll w){
        if(cl == cr){
            TREE[node].fi = w;
            TREE[node].se = cc;
            return;
        }
        int mid = (cl + cr) / 2;
        if(mid >= v)
            add(node * 2, cl, mid, v, cc, w);
        else
            add(node * 2 + 1, mid + 1, cr, v, cc, w);
        TREE[node].fi = TREE[node * 2].fi + TREE[node * 2 + 1].fi;
        TREE[node].se = TREE[node * 2].se + TREE[node * 2 + 1].se;
    }
    ll get(int node, int cl, int cr, int cnt){
        if(cnt == 0) return 0;
        if(cl == cr){
            return TREE[node].fi;
        }
        int mid = (cl + cr) / 2;
        if(TREE[node * 2].se >= cnt){
            return get(node * 2, cl, mid, cnt);
        }
        else{
            return get(node * 2 + 1, mid + 1, cr, cnt - TREE[node * 2].se) + TREE[node * 2].fi;
        }
    }
};

vector<pii> F[N];

segment_tree lows[N];

int k;
bool vis[N];

void dfs(int u, ll las){
    vis[u]=true;
    int deg = T[u].size();
    vector<ll> vals;
    ll total = 0;
    for(auto x : F[u]){
        if(vis[x.fi]) continue;
        dfs(x.fi, x.se);
        total += dp[x.fi][1];
        vals.push_back(dp[x.fi][0] - dp[x.fi][1]);
    }
    sort(vals.begin(), vals.end());
    int need;
    ll ash;
    for(int r = 0; r <= vals.size(); r ++ ){
        // take parent
        need = (deg - k) - 1 - r;
        ash = total + las;
        if(need > 0)
            ash += lows[u].get(1, 0, deg - 1, need);
        if(lows[u].TREE[1].se >= need)
            dp[u][0] = min(dp[u][0], ash);
        // dont take parent
        ash = total;
        need = (deg - k) - r;
        if(need > 0)
            ash += lows[u].get(1, 0, deg - 1, need);
        if(lows[u].TREE[1].se >= need)
            dp[u][1] = min(dp[u][1], ash);
        if(r < vals.size())
            total += vals[r];
    }
}

int L[N];

vector<ll> minimum_closure_costs(int _n, vector<int> _u,vector<int> _v, vector<int> _w) {
    n = _n;
    u = _u;
    v = _v;
    w = _w;
    for(int i = 0 ; i < n - 1; i ++ ){
        T[u[i]].push_back(mp(v[i], i));
        T[v[i]].push_back(mp(u[i], i));
    }
    for(int i = 0 ; i < n; i ++ ){
        ad[T[i].size()].push_back(i);
    }
    for(int i = 0 ; i < n; i ++ ){
        sort(T[i].begin(), T[i].end(), comp);
        lows[i].init(T[i].size());
        for(int j = 0 ; j < T[i].size(); j ++ ){
            lows[i].add(1, 0, lows[i].sz - 1, j, 1, w[T[i][j].se]);
        }
    }

    vector<int> vse;
    vector<ll> outp(n);
    for(int i = n - 1; i >= 0 ; i -- ){
        for(auto x : vse){
            vis[x]=false;
            dp[x][0]=dp[x][1]=(ll)1e18;
        }
        k = i;
        for(auto x : vse){
            if(!vis[x]){
                dfs(x, 0);
                outp[i] += dp[x][1];
            }
        }
        for(auto x : ad[i]){
            active[x]=true;
            vse.push_back(x);
            for(int j = 0; j < T[x].size(); j ++ ){
                if(active[T[x][j].fi]){

                    F[x].push_back(mp(T[x][j].fi, w[T[x][j].se]));
                    F[T[x][j].fi].push_back(mp(x, w[T[x][j].se]));
                    lows[T[x][j].se].add(1, 0, lows[x].sz - 1, L[T[x][j].se], 0, 0);
                    lows[x].add(1, 0, lows[x].sz - 1, j, 0, 0);
                }
                else{
                    L[T[x][j].se] = j;
                }
            }
        }
    }
    return outp;
}

Compilation message

roads.cpp: In function 'void dfs(int, ll)':
roads.cpp:94:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int r = 0; r <= vals.size(); r ++ ){
      |                    ~~^~~~~~~~~~~~~~
roads.cpp:109:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         if(r < vals.size())
      |            ~~^~~~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:131:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         for(int j = 0 ; j < T[i].size(); j ++ ){
      |                         ~~^~~~~~~~~~~~~
roads.cpp:153:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |             for(int j = 0; j < T[x].size(); j ++ ){
      |                            ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 9 ms 11528 KB Output is correct
3 Correct 9 ms 11684 KB Output is correct
4 Correct 9 ms 11572 KB Output is correct
5 Correct 6 ms 10492 KB Output is correct
6 Correct 6 ms 10572 KB Output is correct
7 Correct 6 ms 10572 KB Output is correct
8 Correct 8 ms 11468 KB Output is correct
9 Correct 9 ms 11628 KB Output is correct
10 Correct 6 ms 10488 KB Output is correct
11 Correct 6 ms 10572 KB Output is correct
12 Correct 109 ms 45608 KB Output is correct
13 Correct 193 ms 69112 KB Output is correct
14 Correct 183 ms 63352 KB Output is correct
15 Correct 210 ms 69096 KB Output is correct
16 Correct 212 ms 69804 KB Output is correct
17 Correct 194 ms 69932 KB Output is correct
18 Correct 6 ms 10444 KB Output is correct
19 Correct 169 ms 63876 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 125 ms 78140 KB Output is correct
3 Correct 144 ms 88160 KB Output is correct
4 Correct 153 ms 93316 KB Output is correct
5 Correct 151 ms 93468 KB Output is correct
6 Correct 11 ms 11852 KB Output is correct
7 Correct 9 ms 12108 KB Output is correct
8 Correct 8 ms 11912 KB Output is correct
9 Correct 6 ms 10572 KB Output is correct
10 Correct 6 ms 10572 KB Output is correct
11 Correct 6 ms 10572 KB Output is correct
12 Correct 85 ms 59692 KB Output is correct
13 Correct 147 ms 92548 KB Output is correct
14 Correct 6 ms 10444 KB Output is correct
15 Correct 147 ms 84388 KB Output is correct
16 Correct 154 ms 92688 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 7 ms 10484 KB Output is correct
3 Correct 7 ms 10444 KB Output is correct
4 Incorrect 6 ms 10572 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 7 ms 10484 KB Output is correct
3 Correct 7 ms 10444 KB Output is correct
4 Incorrect 6 ms 10572 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

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

Subtask #6
0 / 25.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 9 ms 11528 KB Output is correct
3 Correct 9 ms 11684 KB Output is correct
4 Correct 9 ms 11572 KB Output is correct
5 Correct 6 ms 10492 KB Output is correct
6 Correct 6 ms 10572 KB Output is correct
7 Correct 6 ms 10572 KB Output is correct
8 Correct 8 ms 11468 KB Output is correct
9 Correct 9 ms 11628 KB Output is correct
10 Correct 6 ms 10488 KB Output is correct
11 Correct 6 ms 10572 KB Output is correct
12 Correct 109 ms 45608 KB Output is correct
13 Correct 193 ms 69112 KB Output is correct
14 Correct 183 ms 63352 KB Output is correct
15 Correct 210 ms 69096 KB Output is correct
16 Correct 212 ms 69804 KB Output is correct
17 Correct 194 ms 69932 KB Output is correct
18 Correct 6 ms 10444 KB Output is correct
19 Correct 169 ms 63876 KB Output is correct
20 Correct 6 ms 10444 KB Output is correct
21 Correct 125 ms 78140 KB Output is correct
22 Correct 144 ms 88160 KB Output is correct
23 Correct 153 ms 93316 KB Output is correct
24 Correct 151 ms 93468 KB Output is correct
25 Correct 11 ms 11852 KB Output is correct
26 Correct 9 ms 12108 KB Output is correct
27 Correct 8 ms 11912 KB Output is correct
28 Correct 6 ms 10572 KB Output is correct
29 Correct 6 ms 10572 KB Output is correct
30 Correct 6 ms 10572 KB Output is correct
31 Correct 85 ms 59692 KB Output is correct
32 Correct 147 ms 92548 KB Output is correct
33 Correct 6 ms 10444 KB Output is correct
34 Correct 147 ms 84388 KB Output is correct
35 Correct 154 ms 92688 KB Output is correct
36 Correct 6 ms 10444 KB Output is correct
37 Correct 7 ms 10484 KB Output is correct
38 Correct 7 ms 10444 KB Output is correct
39 Incorrect 6 ms 10572 KB Output isn't correct
40 Halted 0 ms 0 KB -