제출 #1194974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194974		browntoad	Road Closures (APIO21_roads)	C++20	0 / 100	2096 ms	37576 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n) 
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())

namespace{
    const ll maxn = 1e5+5;
    const ll inf = 1ll<<60;

    int n;
    vector<pii> g[maxn];
    vector<pii> ag[maxn];
    vector<int> par(maxn);
}
int fin(int a){
    if (par[a] == a) return a;
    return par[a] = fin(par[a]);
}
void merg(int a, int b){
    a = fin(a); b = fin(b);
    par[a] = b;
}

map<pii, int> mp;
int dp[maxn][2]; // subtree of u, whether alr matches with a child
pii pp[maxn];
vector<bool> occ(maxn);
vector<pii> poo;
void dfs(int u, int pre){
    occ[u] = 1;
    dp[u][0] = dp[u][1] = 0;

    pp[u] = {-inf, -1};
    for (auto e:ag[u]){
        if (e.f == pre) continue;
        dfs(e.f, u);
        dp[u][0] += max(dp[e.f][1], dp[e.f][0]);
        dp[u][1] += max(dp[e.f][1], dp[e.f][0]);
        if (pp[u].f < e.s + dp[e.f][0] - max(dp[e.f][1], dp[e.f][0])){
            pp[u].f = e.s + dp[e.f][0] - max(dp[e.f][1], dp[e.f][0]);
            pp[u].s = e.f;
        }
    }
    dp[u][1] += pp[u].f;
}
void dfs2(int u, int pre, bool wh){
    if (!wh){
        for (auto e:ag[u]){
            if (e.f == pre) continue;
            if (dp[e.f][0] > dp[e.f][1]) dfs2(e.f, u, 0);
            else dfs2(e.f, u, 1);
        }
    }
    else{
        poo.pb({pp[u].s, u});
        for (auto e:ag[u]){
            if (e.f == pre) continue;
            if (pp[u].s == e.f){
                dfs2(e.f, u, 0);
            }
            else{
                if (dp[e.f][0] > dp[e.f][1]) dfs2(e.f, u, 0);
                else dfs2(e.f, u, 1);
            }
        }
    }
}
std::vector<long long> minimum_closure_costs(signed N, std::vector<signed> U, std::vector<signed> V, std::vector<signed> W) {
    n = N;
    int sm = 0;

    REP(i, n-1){
        sm += W[i];
        g[U[i]].pb({V[i], W[i]});
        g[V[i]].pb({U[i], W[i]});
        mp[{U[i], V[i]}] = i;
        mp[{V[i], U[i]}] = i;
    }
    vector<bool> ban(n-1);

    REP(i, n) par[i] = i;

    vector<int> ret;
    ret.pb(sm);
    REP(t, n-1){
        REP(i, n) ag[i].clear();
        REP(i, n) occ[i] = 0;
        REP(i, n-1){
            if (!ban[i]){
                ag[U[i]].pb({V[i], W[i]});
                ag[V[i]].pb({U[i], W[i]});
            }
        }

        poo.clear();
        REP(i, n) if (!occ[i]) {
            dfs(i, -1);
            if (dp[i][0] > dp[i][1]) dfs2(i, -1, 0);
            else dfs2(i, -1, 1);
            sm -= max(dp[i][0], dp[i][1]);
        }

        for (auto ee:poo){
            ban[mp[{ee.f, ee.s}]] = 1;
        }
        ret.pb(sm);
    }
    return ret;
}

• Subtask 1: 0 / 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