Submission #2489917


Source Code Expand

#include <algorithm>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
const ll INF = 1ll << 62;
 
int main() {
  int N;
  while (cin >> N) {
    vector<ll> x(N);
    for (int i = 0; i < N; i++) {
      cin >> x[i];
    }
    vector<vector<int>> G(N);
    for (int i = 1; i < N; i++) {
      int a;
      cin >> a;
      --a;
      G[a].push_back(i);
    }
    vector<int> child(N, 0);
    for (int i = 0; i < N; i++) {
      int m = 0;
      for (int j : G[i]) {
        m |= 1 << j;
      }
      child[i] = m;
    }
    vector<ll> dp(1 << N, -1);
    dp[1] = 0;
    function<ll(int, int)> solve = [&](int mask, int used) {
      ll &res = dp[mask];
      if (res != -1) return res;
      int mem = 0;
      for (int i = 0; i < N; i++) {
        if ((mask >> i) & 1) mem += x[i];
      }
      res = INF;
      for (int i = 0; i < N; i++) {
        if ((used >> i) & 1) continue;
        if ((mask & child[i]) != child[i]) continue;
        res = min(res, max(mem + x[i],
                           solve(mask ^ child[i] ^ (1 << i), used ^ (1 << i))));
      }
      return res;
    };
    cout << solve(0, 0) << endl;
  }
  return 0;
}

Submission Info

Submission Time
Task D - ディスクの節約
User luogu_bot1
Language C++ (GCC 5.4.1)
Score 0
Code Size 1350 Byte
Status CE

Compile Error

./Main.cpp:12:7: error: expected nested-name-specifier before ‘ll’
 using ll = long long;
       ^
./Main.cpp:13:7: error: ‘ll’ does not name a type
 const ll INF = 1ll << 62;
       ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:18:12: error: ‘ll’ was not declared in this scope
     vector<ll> x(N);
            ^
./Main.cpp:18:14: error: template argument 1 is invalid
     vector<ll> x(N);
              ^
./Main.cpp:18:14: error: template argument 2 is invalid
./Main.cpp:20:17: error: invalid types ‘int[int]’ for array subscript
       cin >> x[i];
                 ^
./Main.cpp:22:22: error: ‘>>’ should be ‘> >’ within a nested template argument list
     vector<vector<int>> G(N);
                      ^
./Main.cpp:32:20: warning: range-based ‘for’ loops only available with -std=c++11 or -std=gnu++11
       for (int j : G[i]) {
                    ^
./Main.cpp:37:14: error: type/value mismatch at argument 1 in template parameter list for ‘template<class _Tp, class _Alloc> class std::vector’
     v...