제출 #957993

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
957993		Itamar	도로 폐쇄 (APIO21_roads)	C++14	5 / 100	47 ms	34232 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;

bool tst;
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];
vi w[siz];
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] });
            }
        }
    }
    for (int j : w[i])op.push_back(j);
    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;
    while (mon>0) {
        dp1[i][k] += op[it];
        dp2[i][k] += op[it];
        it++;
        mon--;
    }
    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);
    sort(W.begin(), W.end());
    for (int i = 0; i < N-1; i++) {
        ans[N - i - 2] = ans[N-i-1]+W[i];
    }
    /*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].push_back(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: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22