Submission #957979

#	Time	Username	Problem	Language	Result	Execution time	Memory
957979		Itamar	Road Closures (APIO21_roads)	C++14	17 / 100	124 ms	85384 KiB

roads

#include "roads.h"
using namespace std;
#include <vector>
#define vll vector<ll>
#define ll long long
#include <algorithm>
#include <set>
#include <queue>
#define vi vector<int>
#define pll pair<ll,ll>
#define x first
#define y second
#define pi pair<int,int>
const int siz = 1e5 + 1;

set<ll> s[siz];
priority_queue<ll> pq1[siz], pq2[siz];
bool bad[siz];
vector<pi> fr[siz];
vi his[siz];
ll sum[siz];
vll dp1[siz];
vll dp2[siz];
int deg[siz];
int w[siz][12];
vll ans;
vector<bool> vis[siz];

void dfs(int i, int k) {
    if (bad[i] || vis[i][k])return;
    vis[i][k] = 1;
    int s = fr[i].size();
    vll op;
    //for (int i = 1; i <= 10; i++)op.push_back(i);
    for (int j = s - 1; j >= 0; j--) {
        int f = fr[i][j].x;
        if (bad[f]) {
            swap(fr[i][j], fr[i].back());
            fr[i].pop_back();
        }
        else {
            if (!vis[f][k]) {
                dfs(f, k);
                dp1[i][k] += dp1[f][k];
                dp2[i][k] += dp1[f][k]; // full price
                op.push_back({ fr[i][j].y + dp2[f][k] - dp1[f][k] });
            }
        }
    }
    sort(op.begin(), op.end());
    op.push_back(1e9);
    int mon = deg[i] - k-1;
    int it = 0;
    while (op[it] < 0) {
        dp1[i][k] += op[it];
        dp2[i][k] += op[it];
        it++;
        mon--;
    }
    ll pl = 1e9;
    for (int j = 1; j <= 10; j++) {
        while (op[it] < j && mon>0 ) {
            dp1[i][k] += op[it];
            dp2[i][k] += op[it];
            it++;
            mon--;
        }
        int m = min(mon, w[i][j]);
        mon -= m;
        if (w[i][j] > m)pl = min(pl, (ll)j);
        dp1[i][k] += m*j;
        dp2[i][k] += m*j;
    }
    pl = min(pl, op[it]);
    if(mon==0)dp1[i][k] += pl;


}

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

    ans.resize(N);
    for (int i = 0; i < N - 1; i++) {
        ans[0] += W[i];
        fr[U[i]].push_back({ V[i],W[i] });
        fr[V[i]].push_back({ U[i],W[i] });
    }
    for (int i = 0; i < N; i++)his[fr[i].size()].push_back(i);
    for (int i = 0; i < N; i++)cur.push_back(i);
    for (int i = 0; i < N; i++) {
        deg[i] = fr[i].size();
        dp1[i].resize(fr[i].size());
        dp2[i].resize(fr[i].size());
        vis[i].resize(fr[i].size());
    }
    for (int k = 1; k < N-1; k++) {
        for (int i : his[k]) {
            bad[i] = 1;
            for (pll f : fr[i]) {
                w[f.x][f.y]++;
            }
        }
        int s = cur.size();
        for (int i = s - 1; i >= 0; i--) {
            if (bad[cur[i]]) {
                swap(cur[i], cur.back()); cur.pop_back();
            }
            else {
                if (!vis[cur[i]][k]) {
                    dfs(cur[i], k);
                    ans[k] += dp1[cur[i]][k];
                }
            }
        }
    }

    return ans;
}

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