oj.uz

Submission #412809

# Submission time Handle Problem Language Result Execution time Memory
412809 2021-05-27T15:32:43 Z two_sides Road Closures (APIO21_roads) C++17
7 / 100
 184 ms 50820 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.assign(N + 1, 0);
        sum.assign(N + 1, 0);
        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 11 ms 15948 KB Output is correct
2 Incorrect 11 ms 16428 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 15948 KB Output is correct
2 Correct 95 ms 44884 KB Output is correct
3 Correct 107 ms 48572 KB Output is correct
4 Correct 125 ms 50748 KB Output is correct
5 Correct 113 ms 50760 KB Output is correct
6 Correct 11 ms 16568 KB Output is correct
7 Correct 11 ms 16588 KB Output is correct
8 Correct 11 ms 16588 KB Output is correct
9 Correct 9 ms 15948 KB Output is correct
10 Correct 10 ms 15968 KB Output is correct
11 Correct 10 ms 16076 KB Output is correct
12 Correct 88 ms 36764 KB Output is correct
13 Correct 112 ms 50784 KB Output is correct
14 Correct 10 ms 15948 KB Output is correct
15 Correct 98 ms 47476 KB Output is correct
16 Correct 107 ms 50820 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 10 ms 15888 KB Output is correct
3 Correct 9 ms 15948 KB Output is correct
4 Incorrect 10 ms 15948 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 10 ms 15888 KB Output is correct
3 Correct 9 ms 15948 KB Output is correct
4 Incorrect 10 ms 15948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

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

Subtask #6
0 / 25.0

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

Subtask #7
0 / 22.0

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