Submission #650706

#	Time	Username	Problem	Language	Result	Execution time	Memory
650706		Alexandruabcde	Road Closures (APIO21_roads)	C++14	31 / 100	2093 ms	45232 KiB

roads

#include "roads.h"

#include <vector>
#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 100005;
typedef long long LL;
constexpr LL INF = 1LL * 1e15;
typedef pair <LL, int> PLLI;

struct muchie {
    int x, y;
    LL cost;
};

muchie E[NMAX];

vector <int> G[NMAX];
vector <int> Degree[NMAX];
vector <int> GoodNodes;
bool Unlocked[NMAX];

priority_queue <PLLI, vector <PLLI>, greater <PLLI> > H[NMAX];

LL dp[NMAX][2];
bool viz[NMAX];

bool Bad (int ind) {
    return (Unlocked[E[ind].x] && Unlocked[E[ind].y]);
}

void Dfs (int k, int Node, int dad = -1) {
    viz[Node] = true;

    for (auto it : G[Node]) {
        int to = (E[it].x == Node ? E[it].y : E[it].x);

        if (to == dad) continue;
        if (viz[to]) continue;
        if (!Unlocked[to]) continue;

        Dfs(k, to, Node);
    }

    int grad = 0;
    vector <LL> V;
    LL sum = 0;

    for (auto it : G[Node]) {
        int to = (E[it].x == Node ? E[it].y : E[it].x);

        if (to == dad) continue;

        ++ grad;
        if (Unlocked[to]) {
            V.push_back(dp[to][1] - dp[to][0]);
            sum += dp[to][0];
        }
    }

    dp[Node][0] = INF;
    dp[Node][1] = INF;

    sort(V.begin(), V.end());
    int ind_V = 0;
    vector <PLLI> remember;

    if (k > 0) {
        dp[Node][0] = sum;
        for (int i = 0; i < max(0, grad - k + 1); ++ i ) {
            while (!H[Node].empty() && Bad(H[Node].top().second))
                H[Node].pop();

            if (H[Node].empty()) {
                dp[Node][0] += V[ind_V];
                ++ ind_V;
            }
            else {
                if (ind_V >= V.size()) {
                    dp[Node][0] += H[Node].top().first;
                    remember.push_back(H[Node].top());
                    H[Node].pop();
                }
                else if (V[ind_V] <= H[Node].top().first) {
                    dp[Node][0] += V[ind_V];
                    ++ ind_V;
                }
                else {
                    dp[Node][0] += H[Node].top().first;
                    remember.push_back(H[Node].top());
                    H[Node].pop();
                }
            }
        }

        while (ind_V < V.size() && V[ind_V] < 0) {
            dp[Node][0] += V[ind_V];
            ++ ind_V;
        }

        while (!remember.empty()) {
            H[Node].push(remember.back());
            remember.pop_back();
        }
        ind_V = 0;
    }

    if (dad == -1) {
        dp[Node][1] = sum;
        for (int i = 0; i < max(0, grad - k); ++ i ) {
            while (!H[Node].empty() && Bad(H[Node].top().second))
                H[Node].pop();

            if (H[Node].empty()) {
                dp[Node][1] += V[ind_V];
                ++ ind_V;
            }
            else {
                if (ind_V >= V.size()) {
                    dp[Node][1] += H[Node].top().first;
                    remember.push_back(H[Node].top());
                    H[Node].pop();
                }
                else if (V[ind_V] <= H[Node].top().first) {
                    dp[Node][1] += V[ind_V];
                    ++ ind_V;
                }
                else {
                    dp[Node][1] += H[Node].top().first;
                    remember.push_back(H[Node].top());
                    H[Node].pop();
                }
            }
        }

        while (ind_V < V.size() && V[ind_V] < 0) {
            dp[Node][1] += V[ind_V];
            ++ ind_V;
        }

        while (!remember.empty()) {
            H[Node].push(remember.back());
            remember.pop_back();
        }
        ind_V = 0;
    }

    for (auto it : G[Node]) {
        int to = (E[it].x == Node ? E[it].y : E[it].x);

        if (to != dad) continue;

        dp[Node][1] = sum + E[it].cost;
        for (int i = 0; i < max(0, grad - k); ++ i ) {
            while (!H[Node].empty() && Bad(H[Node].top().second))
                H[Node].pop();

            if (H[Node].empty()) {
                dp[Node][1] += V[ind_V];
                ++ ind_V;
            }
            else {
                if (ind_V >= V.size()) {
                    dp[Node][1] += H[Node].top().first;
                    remember.push_back(H[Node].top());
                    H[Node].pop();
                }
                else if (V[ind_V] <= H[Node].top().first) {
                    dp[Node][1] += V[ind_V];
                    ++ ind_V;
                }
                else {
                    dp[Node][1] += H[Node].top().first;
                    remember.push_back(H[Node].top());
                    H[Node].pop();
                }
            }
        }

        while (ind_V < V.size() && V[ind_V] < 0) {
            dp[Node][1] += V[ind_V];
            ++ ind_V;
        }

        while (!remember.empty()) {
            H[Node].push(remember.back());
            remember.pop_back();
        }

        break;
    }
}

LL Solve (int K) {
    LL ans = 0;
    for (auto it : GoodNodes) {
        if (viz[it]) continue;

        Dfs(K, it, -1);
        ans += dp[it][1];
    }

    for (auto it : GoodNodes)
        viz[it] = false;

    return ans;
}

void Add (int Node) {
    GoodNodes.push_back(Node);
    Unlocked[Node] = true;
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {

    for (int i = 1; i < N; ++ i ) {
        E[i] = {U[i-1], V[i-1], 1LL * W[i-1]};

        G[U[i-1]].push_back(i);
        G[V[i-1]].push_back(i);

        H[U[i-1]].push({W[i-1], i});
        H[V[i-1]].push({W[i-1], i});
    }

    for (int i = 0; i < N; ++ i ) {
        Degree[G[i].size()].push_back(i);
    }

    vector <LL> ans;
    ans.resize(N);

    for (int k = N-1; k >= 0; -- k ) {
        ans[k] = Solve(k);

        for (auto it : Degree[k])
            Add(it);
    }

    return ans;
}

Compilation message (stderr)

roads.cpp: In function 'void Dfs(int, int, int)':
roads.cpp:81:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |                 if (ind_V >= V.size()) {
      |                     ~~~~~~^~~~~~~~~~~
roads.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         while (ind_V < V.size() && V[ind_V] < 0) {
      |                ~~~~~~^~~~~~~~~~
roads.cpp:121:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |                 if (ind_V >= V.size()) {
      |                     ~~~~~~^~~~~~~~~~~
roads.cpp:138:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         while (ind_V < V.size() && V[ind_V] < 0) {
      |                ~~~~~~^~~~~~~~~~
roads.cpp:165:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |                 if (ind_V >= V.size()) {
      |                     ~~~~~~^~~~~~~~~~~
roads.cpp:182:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |         while (ind_V < V.size() && V[ind_V] < 0) {
      |                ~~~~~~^~~~~~~~~~

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