Submission #961882

#	Time	Username	Problem	Language	Result	Execution time	Memory
961882		socpite	Road Closures (APIO21_roads)	C++14	100 / 100	174 ms	79608 KiB

roads

#include<bits/stdc++.h>
using namespace std;
 
const int maxn = 3e5+5;
const long long INF = 1e18;
 
vector<pair<int, long long>> g[maxn];
vector<long long> dp[2][maxn];
long long tdp[2][maxn];
int pos[maxn];
 
struct Fenwick{
    vector<int> cnt;
    vector<long long> sum;
    int sz;
    Fenwick(int _sz): sz(_sz){
        cnt.assign(sz + 1, 0);
        sum.assign(sz + 1, 0);
    }
    void add(int idx, long long val){
        assert(idx);
        for(idx; idx <= sz; idx += idx&(-idx)){
            cnt[idx]++;
            sum[idx] += val;
        }
    }
    pair<int, long long> query(int k){
        int pos = 0;
        long long re = 0;
        for(int i = 17; i >= 0; i--){
            if((pos^(1<<i)) > sz)continue;
            if(cnt[pos^(1<<i)] <= k){
                pos^=(1<<i);
                k -= cnt[pos];
                re += sum[pos];
            }
        }
        if(k > 0)return {pos, INF};
        return {pos, re};
    }
};
 
void dfs(int x, int p, long long pe){
    vector<pair<int, int>> child_d;
    vector<pair<long long, int>> child_w = {{pe, p}};
    for(auto v: g[x]){
        if(v.first == p)continue;
        dfs(v.first, x, v.second);
        child_d.push_back({g[v.first].size(), v.first});
        child_w.push_back({v.second, v.first});
    }
    sort(child_w.begin(), child_w.end());
    sort(child_d.begin(), child_d.end());
    Fenwick fw(child_w.size());
    for(int i = 0; i < child_w.size(); i++){
        pos[child_w[i].second] = i+1;
    }
    fw.add(pos[p], pe);
    int ptr = 0;
    for(int i = 0; i < g[x].size(); i++){
        tdp[0][i] = tdp[1][i] = INF;
        while(ptr < child_d.size() && child_d[ptr].first == i){
            int id = child_d[ptr].second;
            fw.add(pos[id], child_w[pos[id] - 1].first);
            ptr++;
        }
        long long sum = 0;
        vector<long long> save_cost;
        for(int j = ptr; j < child_d.size(); j++)save_cost.push_back(dp[1][child_d[j].second][i] - dp[0][child_d[j].second][i]);
        sort(save_cost.begin(), save_cost.end());
        for(int j = 0; j <= save_cost.size(); j++){
            auto cost = fw.query(int(g[x].size()) - i - j);
            cost.second += sum;
            tdp[0][i] = min(tdp[0][i], cost.second);
            if(cost.first < pos[p]){
                tdp[1][i] = min(tdp[1][i], fw.query(int(g[x].size()) - i - j - 1).second + pe + sum);
            }
            else tdp[1][i] = min(tdp[1][i], cost.second);
            if(j < save_cost.size())sum += save_cost[j];
        }
    }
    for(auto v: g[x]){
        if(v.first == p)continue;
        if(dp[0][v.first].size() > dp[0][x].size())dp[0][x].swap(dp[0][v.first]);
        for(int i = 0; i < dp[0][v.first].size(); i++)dp[0][x][i] += dp[0][v.first][i];
    }
    dp[1][x].resize(g[x].size());
    while(dp[0][x].size() < g[x].size())dp[0][x].push_back(0);
    for(int i = 0; i < g[x].size(); i++){
        dp[1][x][i] = dp[0][x][i];
        for(int j = 0; j < 2; j++)dp[j][x][i] += tdp[j][i];
    }
    // 
}
 
vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W){
    vector<long long> re(N, 0);
    for(int i = 0; i < N - 1; i++){
        U[i]++;
        V[i]++;
        g[U[i]].push_back({V[i], W[i]});
        g[V[i]].push_back({U[i], W[i]});
    }
    dfs(1, 0, INF);
    for(int i = 0; i < dp[0][1].size(); i++){
        re[i] = dp[0][1][i];
    }
    return re;
}

Compilation message (stderr)

roads.cpp: In member function 'void Fenwick::add(int, long long int)':
roads.cpp:22:13: warning: statement has no effect [-Wunused-value]
   22 |         for(idx; idx <= sz; idx += idx&(-idx)){
      |             ^~~
roads.cpp: In function 'void dfs(int, int, long long int)':
roads.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int i = 0; i < child_w.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~
roads.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i = 0; i < g[x].size(); i++){
      |                    ~~^~~~~~~~~~~~~
roads.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         while(ptr < child_d.size() && child_d[ptr].first == i){
      |               ~~~~^~~~~~~~~~~~~~~~
roads.cpp:69:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(int j = ptr; j < child_d.size(); j++)save_cost.push_back(dp[1][child_d[j].second][i] - dp[0][child_d[j].second][i]);
      |                          ~~^~~~~~~~~~~~~~~~
roads.cpp:71:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(int j = 0; j <= save_cost.size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~~~~
roads.cpp:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             if(j < save_cost.size())sum += save_cost[j];
      |                ~~^~~~~~~~~~~~~~~~~~
roads.cpp:85:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for(int i = 0; i < dp[0][v.first].size(); i++)dp[0][x][i] += dp[0][v.first][i];
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~
roads.cpp:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i = 0; i < g[x].size(); i++){
      |                    ~~^~~~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:105:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(int i = 0; i < dp[0][1].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 17 / 17
• Subtask 6: 25 / 25
• Subtask 7: 22 / 22