oj.uz

답안 #558835

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
558835 2022-05-08T15:29:49 Z hoanghq2004 도로 폐쇄 (APIO21_roads) C++14
0 / 100
 598 ms 367404 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "roads.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 3e5 + 10;

int n, k;
long long f[N][2];
set <pair <int, int> > g[N];
vector <int> s[N];
int vis[N], ti;

struct Set {
    struct node {
        int to[2];
        int cnt;
        long long sum;
    };
    int nNode = 0;
    vector <node> T = {node()};
    void add(long long x) {
        int u = 0;
        for (int i = 50; i >= 0; --i) {
            if (!T[u].to[x >> i & 1]) T[u].to[x >> i & 1] = ++nNode, T.push_back(node());
            u = T[u].to[x >> i & 1];
            ++T[u].cnt;
            T[u].sum += x;
        }
    }
    void rev(long long x) {
        int u = 0;
        for (int i = 50; i >= 0; --i) {
            u = T[u].to[x >> i & 1];
            --T[u].cnt;
            T[u].sum -= x;
        }
    }
    long long get(int k) {
        int u = 0;
        long long ans = 0;
        for (int i = 50; i >= 0; --i) {
            if (T[T[u].to[1]].cnt <= k) {
                ans += T[T[u].to[1]].sum;
                k -= T[T[u].to[1]].cnt;
                u = T[u].to[0];
            } else u = T[u].to[1];
        }
        return ans;
    }
} S[N];

long long d[N];

inline void dfs(int u, int p) {
    vis[u] = ti;
    f[u][0] = f[u][1] = d[u];
    for (auto [v, w]: g[u])
        if (v != p) dfs(v, u);
    vector <long long> tmp;
    for (auto [v, w]: g[u]) {
        if (v == p) continue;
        f[u][0] += f[v][0] + w;
        f[u][1] += f[v][0] + w;
        if (- f[v][1] + f[v][0] + w > 0) S[u].add(- f[v][1] + f[v][0] + w), tmp.push_back(- f[v][1] + f[v][0] + w);
    }
    if (k) {
        f[u][0] -= S[u].get(k);
        f[u][1] -= S[u].get(k - 1);
    }
    for (auto x: tmp) S[u].rev(x);
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {
    n = N;
    for (int i = 0; i < N - 1; ++i) {
        int u = U[i], v = V[i], w = W[i];
        ++u, ++v;
        g[u].insert({v, w});
        g[v].insert({u, w});
    }
    for (int i = 1; i <= n; ++i) s[g[i].size()].push_back(i);
    set <int> rem;
    for (int i = 1; i <= n; ++i) rem.insert(i);
    vector <long long> ans;
    for (k = 0; k < n; ++k) {
        ++ti;
        long long cost = 0;
        for (auto u: s[k]) {
            for (auto [v, w]: g[u]) {
                d[v] += w;
                g[v].erase({u, w});
                S[v].add(w);
            }
            g[u].clear();
            rem.erase(u);
        }
        for (auto u: rem) if (vis[u] != ti) dfs(u, 0), cost += f[u][0];
        ans.push_back(cost);
    }
    return ans;
}


//int main() {
////    freopen("test.inp", "r", stdin);
//  int N;
//  assert(1 == scanf("%d", &N));
//
//  std::vector<int> U(N - 1), V(N - 1), W(N - 1);
//  for (int i = 0; i < N - 1; ++i) {
//    assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
//  }
//
//  std::vector<long long> closure_costs = minimum_closure_costs(N, U, V, W);
//  for (int i = 0; i < static_cast<int>(closure_costs.size()); ++i) {
//    if (i > 0) {
//      printf(" ");
//    }
//    printf("%lld",closure_costs[i]);
//  }
//  printf("\n");
//  return 0;
//}

Compilation message

roads.cpp: In function 'void dfs(int, int)':
roads.cpp:66:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |     for (auto [v, w]: g[u])
      |               ^
roads.cpp:69:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |     for (auto [v, w]: g[u]) {
      |               ^
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:100:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  100 |             for (auto [v, w]: g[u]) {
      |                       ^

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 40148 KB Output is correct
2 Correct 39 ms 42220 KB Output is correct
3 Correct 36 ms 42184 KB Output is correct
4 Incorrect 34 ms 40664 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 40228 KB Output is correct
2 Correct 533 ms 309504 KB Output is correct
3 Correct 557 ms 351320 KB Output is correct
4 Correct 598 ms 367404 KB Output is correct
5 Correct 435 ms 222684 KB Output is correct
6 Correct 39 ms 45872 KB Output is correct
7 Correct 42 ms 46836 KB Output is correct
8 Incorrect 38 ms 43480 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 40160 KB Output is correct
2 Correct 30 ms 40148 KB Output is correct
3 Incorrect 29 ms 40148 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 40160 KB Output is correct
2 Correct 30 ms 40148 KB Output is correct
3 Incorrect 29 ms 40148 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 502 ms 152024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 502 ms 152024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 40148 KB Output is correct
2 Correct 39 ms 42220 KB Output is correct
3 Correct 36 ms 42184 KB Output is correct
4 Incorrect 34 ms 40664 KB Output isn't correct
5 Halted 0 ms 0 KB -