Submission #416602

#	Time	Username	Problem	Language	Result	Execution time	Memory
416602		doowey	Road Closures (APIO21_roads)	C++14	12 / 100	311 ms	93468 KiB

roads

#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 (stderr)

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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22