oj.uz

답안 #558776

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
558776 2022-05-08T10:07:15 Z hoanghq2004 도로 폐쇄 (APIO21_roads) C++14
0 / 100
 1654 ms 37344 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 = 2010;

int n;
long long f[N][N];
vector <long long> tmp[N];
vector <pair <int, int> > g[N];

void dfs(int u, int p) {
    for (auto [v, w]: g[u])
        if (v != p) dfs(v, u);
    for (auto [v, w]: g[u]) {
        if (v == p) continue;
        for (int i = 0; i < n; ++i) f[u][i] += f[v][i] + w;
        for (int i = 1; i < n; ++i)
            tmp[i].push_back(- f[v][i - 1] + f[v][i] + w);
    }
    for (int i = 1; i < n; ++i) {
        sort(tmp[i].begin(), tmp[i].end(), greater<>());
        for (int j = 0; j < i && j < tmp[i].size() && tmp[i][j] > 0; ++j)
            f[u][i] -= tmp[i][j];
        tmp[i].clear();
    }
//    for (int i = 1; i < n; ++i) f[u][i] = max(f[u][i], f[u][i - 1]);
}

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].push_back({v, w});
        g[v].push_back({u, w});
    }
    dfs(1, 0);
    vector <long long> ans;
    for (int i = 0; i < n; ++i) ans.push_back(f[1][i]);
    return ans;
}

//
//int main() {
//  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:22:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |     for (auto [v, w]: g[u])
      |               ^
roads.cpp:24:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |     for (auto [v, w]: g[u]) {
      |               ^
roads.cpp:32:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for (int j = 0; j < i && j < tmp[i].size() && tmp[i][j] > 0; ++j)
      |                                  ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 175 ms 30904 KB Output is correct
3 Correct 221 ms 32820 KB Output is correct
4 Correct 106 ms 32752 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 99 ms 27644 KB Output is correct
9 Correct 139 ms 32780 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Runtime error 114 ms 10992 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 52 ms 37344 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1654 ms 16964 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1654 ms 16964 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 175 ms 30904 KB Output is correct
3 Correct 221 ms 32820 KB Output is correct
4 Correct 106 ms 32752 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 99 ms 27644 KB Output is correct
9 Correct 139 ms 32780 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Runtime error 114 ms 10992 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -