제출 #981508

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
981508		sleepntsheep	도로 폐쇄 (APIO21_roads)	C++11	12 / 100	443 ms	61664 KiB

roads

#include <stdlib.h>
#include <time.h>
#include <string>
#define assert(x) if(!(x))__builtin_trap()

#define NN 100000
#define MM (2*NN)

#define PL (1<<23)
int L[PL], R[PL], S[PL], cur, P[PL];
long long Sum[PL], K[PL];

void pt(int t){if(!t)return; pt(L[t]);printf(" %lld",K[t]);pt(R[t]);}
int node(long long key) {
    int p = ++cur;
    Sum[p] = K[p] = key;
    L[p] = R[p] = 0;
    S[p] = 1;
    P[p] = rand();
    return p;
}
void pul(int v) {
    if (v) {
        S[v] = S[L[v]] + S[R[v]] + 1;
        Sum[v] = K[v] + Sum[L[v]] + Sum[R[v]];
    }
}
void merge(int *v, int l, int r) {
    if (l == 0 || r == 0)
        *v = l ^ r;
    else if (P[l] < P[r])
        merge(L+r, l, L[r]), *v = r;
    else
        merge(R+l, R[l], r), *v = l;
    pul(*v);
}
void split(int v, int *l, int *r, long long key) {
    if (!v)
         *l = 0, *r = 0;
    else if (K[v] <= key)
        split(R[v], R+v, r, key), *l = v;
    else
        split(L[v], l, L+v, key), *r = v;
    pul(v);
}
void spliti(int v, int *l, int *r, int sz) {
    if (!v)
         *l = 0, *r = 0;
    else if (S[L[v]] < sz)
        spliti(R[v], R+v, r, sz - 1 - S[L[v]]), *l = v;
    else
        spliti(L[v], l, L+v, sz), *r = v;
    pul(v);
}
void add(int *v, long long key)
{
    int t1, t2, t3;
    split(*v, &t2, &t3, key);
    split(t2, &t1, &t2, key - 1);
    merge(&t2, t2, node(key));
    merge(&t2, t1, t2);
    merge(v, t2, t3);
}
void remove(int *v, long long key) {
    int t1, t2, t3, t4, t5;
    split(*v, &t2, &t3, key);
    split(t2, &t1, &t2, key - 1);
    spliti(t2, &t4, &t5, 1);
    merge(&t1, t1, t5);
    merge(v, t1, t3);
}
long long min_k_sum(int *v, int k) {
    if (k >= S[*v])
        return Sum[*v];
    int t1, t2;
    spliti(*v, &t1, &t2, k);
    long long zz = Sum[t1];
    merge(v, t1, t2);
    return zz;
}

#include "roads.h"
#include <vector>

long long dp_loose[NN], dp_tight[NN], delsum[NN];
int deg[NN], heap[NN], time_visited[NN];

#include<set>
#include<utility>

std::set<std::pair<int, int> > gg[NN];

void forest_remove(int i) {
    for (auto [w, j] : gg[i]) {
        delsum[j] += w;
        add(heap + j, -w);
        gg[j].erase(std::make_pair(w, i));
    }
}

void dfs(int u, int p, int k) {
    long long base;

    time_visited[u] = k;
    for (auto [w, v] : gg[u])
        if (v != p)
            dfs(v, u, k);

    base = delsum[u];

    for (auto [w, v] : gg[u]) if (v != p) {
        base += w + dp_tight[v];
        long long xx = dp_loose[v] - w - dp_tight[v];
        if (xx <= 0)
            add(heap + u, xx);
    }

    dp_tight[u] = base + min_k_sum(heap+u, k);
    dp_loose[u] = base + min_k_sum(heap+u, k - 1);

    for (auto [w, v] : gg[u]) {
        long long xx = dp_loose[v] - w - dp_tight[v];
        if (xx <= 0)
            remove(heap + u, xx);
    }
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    srand(time(0));
    std::vector<long long> ans(N);

    for (int i = 0; i < N - 1; ++i) {
        ++deg[U[i]], ++deg[V[i]];
        gg[U[i]].emplace(W[i], V[i]);
        gg[V[i]].emplace(W[i], U[i]);
    }

    std::set<int> interesting;
    std::vector<std::basic_string<int> > eh(N);

    for (int i = 0; i < N; ++i) {
        time_visited[i] = -1;
        eh[deg[i]].push_back(i);
        interesting.insert(i);
    }

    for (int k = 0; k < N; ++k) {
        for (auto ii : eh[k]) {
            forest_remove(ii);
            interesting.erase(ii);
        }

        for (auto ii : interesting)
            if (time_visited[ii] != k) {
                dfs(ii, -1, k);
                ans[k] += dp_tight[ii];
            }
    }

    return ans;
}

/*
 * sum deg(v) = 2m = 2n-2
 *
 * let f(x) = count of vertices with degree >= x
 *
 * Lemma:
 *  sum f(x) for all x in [0..n-1] = sum deg(v) = 2m
 *
 * Proof:
 *  - Contribution of node u to sum f(x) is deg(u)
 *
 *  for each edge (u, v), degree u and v increases by one
 *  subsequently, each edge contribute two to sum f(x)
 *
 *
 *
 * N = 100000:
 *  sort vertices by deg
 *
 *  maintain induced subgraph of vertices with deg >= k for each k
 *  do dp on the forest, need to maintain heap of edges connecting node going outside the forest too
 */

컴파일 시 표준 에러 (stderr) 메시지

roads.cpp: In function 'void forest_remove(int)':
roads.cpp:94:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   94 |     for (auto [w, j] : gg[i]) {
      |               ^
roads.cpp: In function 'void dfs(int, int, int)':
roads.cpp:105:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  105 |     for (auto [w, v] : gg[u])
      |               ^
roads.cpp:111:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  111 |     for (auto [w, v] : gg[u]) if (v != p) {
      |               ^
roads.cpp:121:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  121 |     for (auto [w, v] : gg[u]) {
      |               ^

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