oj.uz

Submission #412808

# Submission time Handle Problem Language Result Execution time Memory
412808 2021-05-27T15:31:05 Z two_sides Road Closures (APIO21_roads) C++17
7 / 100
 182 ms 50896 KB 
#include "roads.h"
#include <bits/stdc++.h>

using namespace std;

template <class X, class Y>
bool cmin(X &a, const Y &b) {
    return a > b ? a = b, 1 : 0;
}

const long long INF = 1e18;
const int MAXN = 200005;

struct Fenwick {
    vector <int> cnt; int N, LOG;
    vector <long long> sum;

    void init(int N) {
        this->N = N;
        cnt.resize(N + 1);
        sum.resize(N + 1);
        LOG = __lg(N);
    }

    void add(int i, int v) {
        for (; i <= N; i += i & -i) {
            cnt[i]++; sum[i] += v;
        }
    }

    long long get(int k) {
        if (k < 0) return 0;
        int p = 0; long long ans = 0;
        for (int l = 1 << LOG; l > 0; l >>= 1)
            if (p + l <= N && k >= cnt[p + l]) {
                k -= cnt[p += l]; ans += sum[p];
            }
        return k > 0 ? INF : ans;
    }
};

int par[MAXN], val[MAXN], ord[MAXN];
vector <pair <int, int>> adj[MAXN];
long long DP[MAXN][2];
int prv[MAXN], nxt[MAXN], ptr, lim;
int tin[MAXN], tout[MAXN], ver[MAXN];
Fenwick BIT[MAXN];

void del(int i) {
    nxt[prv[i]] = nxt[i];
    prv[nxt[i]] = prv[i];
}

void DFS1(int u) {
    ver[tin[u] = ++ptr] = u;
    int cnt = 0;
    for (auto e : adj[u]) {
        int v, w; tie(w, v) = e;
        if (v != par[u]) {
            par[v] = u; val[v] = w;
            ord[v] = ++cnt; DFS1(v);
        }
    }
    tout[u] = ptr;
}

void DFS2(int u) {
    vector <long long> tmp;
    long long sum = 0;
    while (nxt[ptr] <= tout[u]) {
        ptr = nxt[ptr];
        int v = ver[ptr]; DFS2(v);
        if (par[v] == u) {
            sum += DP[v][0];
            tmp.push_back(DP[v][1] - DP[v][0]);
        } else sum += min(DP[v][1], DP[v][0]);
    }
    int can = adj[u].size() - lim;
    DP[u][0] = min(INF, sum + BIT[u].get(can));
    DP[u][1] = min(INF, sum + BIT[u].get(can - 1));
    for (int i = 0; i < tmp.size(); i++) {
        sum += tmp[i];
        cmin(DP[u][0], sum + BIT[u].get(can - i - 1));
        cmin(DP[u][1], sum + BIT[u].get(can - i - 2));
    }
    if (u) DP[u][1] = DP[u][1] + val[u];
    else DP[u][1] = INF;
}

long long compute() {
    ptr = 0; long long ans = 0;
    if (lim == 1) cerr << nxt[1] << '\n';
    while (nxt[ptr] <= tout[0]) {
        ptr = nxt[ptr];
        int u = ver[ptr]; DFS2(u);
        ans += min(DP[u][0], DP[u][1]);
    }
    return ans;
}

vector <long long> minimum_closure_costs(int N,
vector <int> U, vector <int> V, vector <int> W) {
    vector <int> nodes;
    for (int i = 0; i < N; i++) {
        adj[i].clear();
        prv[i + 1] = i; nxt[i + 1] = i + 2;
        nodes.push_back(i);
    }
    prv[N + 1] = N; nxt[0] = 1;
    for (int i = 0; i + 1 < N; i++) {
        adj[U[i]].emplace_back(W[i], V[i]);
        adj[V[i]].emplace_back(W[i], U[i]);
    }
    for (int i = 0; i < N; i++) {
       BIT[i].init(adj[i].size());
       sort(adj[i].begin(), adj[i].end());
    }
    DFS1(ptr = 0);
    sort(nodes.begin(), nodes.end(),
    [&](int u, int v) {
        return adj[u].size() < adj[v].size();
    });
    vector <long long> costs(N);
    for  (int i = 0, j = 0; i < N; i++) {
        while (j < N && adj[nodes[j]].size() <= i) {
            int u = nodes[j++];
            if (u && adj[par[u]].size() > i)
                BIT[par[u]].add(ord[u], val[u]);
            del(tin[u]);
        }
        lim = i; costs[i] = compute();
    }
    return costs;
}

Compilation message

roads.cpp: In function 'void DFS2(int)':
roads.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int i = 0; i < tmp.size(); i++) {
      |                     ~~^~~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:125:46: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  125 |         while (j < N && adj[nodes[j]].size() <= i) {
      |                         ~~~~~~~~~~~~~~~~~~~~~^~~~
roads.cpp:127:41: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  127 |             if (u && adj[par[u]].size() > i)
      |                      ~~~~~~~~~~~~~~~~~~~^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15948 KB Output is correct
2 Incorrect 12 ms 16368 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16004 KB Output is correct
2 Correct 98 ms 44844 KB Output is correct
3 Correct 110 ms 48568 KB Output is correct
4 Correct 125 ms 50896 KB Output is correct
5 Correct 118 ms 50792 KB Output is correct
6 Correct 12 ms 16596 KB Output is correct
7 Correct 11 ms 16588 KB Output is correct
8 Correct 11 ms 16588 KB Output is correct
9 Correct 10 ms 15948 KB Output is correct
10 Correct 10 ms 16032 KB Output is correct
11 Correct 10 ms 16068 KB Output is correct
12 Correct 85 ms 36948 KB Output is correct
13 Correct 140 ms 50772 KB Output is correct
14 Correct 10 ms 15920 KB Output is correct
15 Correct 99 ms 47308 KB Output is correct
16 Correct 109 ms 50784 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15948 KB Output is correct
2 Correct 11 ms 15984 KB Output is correct
3 Correct 9 ms 15948 KB Output is correct
4 Incorrect 10 ms 16004 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15948 KB Output is correct
2 Correct 11 ms 15984 KB Output is correct
3 Correct 9 ms 15948 KB Output is correct
4 Incorrect 10 ms 16004 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 182 ms 34048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 182 ms 34048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15948 KB Output is correct
2 Incorrect 12 ms 16368 KB Output isn't correct
3 Halted 0 ms 0 KB -