Submission #3051325
Source Code Expand
#include<iostream> #include<string> #include<cstdio> #include<vector> #include<cmath> #include<algorithm> #include<functional> #include<iomanip> #include<queue> #include<ciso646> #include<random> #include<map> #include<set> #include<complex> #include<bitset> using namespace std; typedef long long ll; typedef unsigned int ui; const ll MOD = 998244353; const ll INF = (ll)1000000007 * 1000000007; typedef pair<int, int> P; #define stop char nyaa;cin>>nyaa; #define rep(i,n) for(int i=0;i<n;i++) #define per(i,n) for(int i=n-1;i>=0;i--) #define Rep(i,sta,n) for(int i=sta;i<n;i++) #define rep1(i,n) for(int i=1;i<=n;i++) #define per1(i,n) for(int i=n;i>=1;i--) #define Rep1(i,sta,n) for(int i=sta;i<=n;i++) typedef long double ld; typedef complex<ld> Point; const ld eps = 1e-11; const ld pi = acos(-1.0); typedef pair<ll, ll> LP; typedef pair<ld, ld> LDP; int n; vector<int> G[20]; int x[20]; bool used[1 << 20]; int memo[1 << 20]; int bfs(int t) { int k = t; if (used[k])return memo[k]; int res = (int)MOD; rep(i, n) { if ((k&(1 << i))&&G[i].size()==0) { k ^= (1 << i); } } if (k == 0)res = 0; int sum = 0; rep(i, n) { if (k&(1 << i)) { sum += x[i]; } } rep(i, n) { if (k&(1 << i)) { int len = G[i].size(); int csum = sum; int nex = k; rep(j, len) { int v = G[i][j]; csum += x[v]; nex |= (1 << v); } nex ^= (1 << i); res = min(res, max(csum, bfs(nex))); } } used[t] = true; memo[t] = res; return res; } int main() { cin >> n; rep(i, n) { cin >> x[i]; } Rep(i, 1, n) { int a; cin >> a; a--; G[a].push_back(i); } fill(used, used + (1 << n), false); cout << bfs(1) << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - ディスクの節約 |
User | heno239 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1738 Byte |
Status | WA |
Exec Time | 3 ms |
Memory | 3584 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 600 | ||||
Status |
|
Set Name | Test Cases |
---|---|
All | 00_sample01, 00_sample02, 00_sample03, 01_handmade00, 01_handmade01, 02_tayama_killer00, 10_complete00, 10_complete01, 10_complete02, 10_complete03, 20_urchin-small00, 20_urchin-small01, 20_urchin-small02, 20_urchin-small03, 20_urchin-small04, 21_urchin-large00, 21_urchin-large01, 21_urchin-large02, 21_urchin-large03, 21_urchin-large04, 30_random-small00, 30_random-small01, 30_random-small02, 30_random-small03, 30_random-small04, 30_random-small05, 30_random-small06, 30_random-small07, 30_random-small08, 30_random-small09, 30_random-small10, 30_random-small11, 30_random-small12, 30_random-small13, 30_random-small14, 30_random-small15, 30_random-small16, 30_random-small17, 30_random-small18, 30_random-small19, 30_random-small20, 30_random-small21, 30_random-small22, 30_random-small23, 30_random-small24, 30_random-small25, 30_random-small26, 30_random-small27, 30_random-small28, 30_random-small29, 31_random-large00, 31_random-large01, 31_random-large02, 31_random-large03, 31_random-large04, 40_boundary00, 40_boundary01 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample01 | AC | 1 ms | 256 KB |
00_sample02 | AC | 1 ms | 256 KB |
00_sample03 | AC | 1 ms | 256 KB |
01_handmade00 | AC | 1 ms | 256 KB |
01_handmade01 | AC | 1 ms | 256 KB |
02_tayama_killer00 | AC | 1 ms | 256 KB |
10_complete00 | AC | 3 ms | 3328 KB |
10_complete01 | AC | 1 ms | 256 KB |
10_complete02 | AC | 1 ms | 256 KB |
10_complete03 | AC | 1 ms | 256 KB |
20_urchin-small00 | AC | 1 ms | 256 KB |
20_urchin-small01 | AC | 1 ms | 256 KB |
20_urchin-small02 | AC | 1 ms | 256 KB |
20_urchin-small03 | AC | 1 ms | 256 KB |
20_urchin-small04 | AC | 1 ms | 256 KB |
21_urchin-large00 | AC | 2 ms | 1280 KB |
21_urchin-large01 | AC | 2 ms | 1280 KB |
21_urchin-large02 | AC | 2 ms | 1280 KB |
21_urchin-large03 | AC | 2 ms | 1280 KB |
21_urchin-large04 | AC | 2 ms | 1280 KB |
30_random-small00 | AC | 1 ms | 256 KB |
30_random-small01 | AC | 1 ms | 256 KB |
30_random-small02 | AC | 1 ms | 256 KB |
30_random-small03 | AC | 1 ms | 256 KB |
30_random-small04 | AC | 1 ms | 256 KB |
30_random-small05 | AC | 1 ms | 256 KB |
30_random-small06 | AC | 1 ms | 256 KB |
30_random-small07 | AC | 1 ms | 256 KB |
30_random-small08 | AC | 1 ms | 256 KB |
30_random-small09 | AC | 1 ms | 256 KB |
30_random-small10 | AC | 1 ms | 256 KB |
30_random-small11 | AC | 1 ms | 256 KB |
30_random-small12 | AC | 1 ms | 256 KB |
30_random-small13 | AC | 1 ms | 256 KB |
30_random-small14 | AC | 1 ms | 256 KB |
30_random-small15 | AC | 1 ms | 256 KB |
30_random-small16 | AC | 1 ms | 256 KB |
30_random-small17 | AC | 1 ms | 256 KB |
30_random-small18 | AC | 1 ms | 256 KB |
30_random-small19 | AC | 1 ms | 256 KB |
30_random-small20 | AC | 1 ms | 256 KB |
30_random-small21 | AC | 1 ms | 256 KB |
30_random-small22 | AC | 1 ms | 256 KB |
30_random-small23 | AC | 1 ms | 256 KB |
30_random-small24 | AC | 1 ms | 256 KB |
30_random-small25 | AC | 1 ms | 256 KB |
30_random-small26 | AC | 1 ms | 256 KB |
30_random-small27 | AC | 1 ms | 256 KB |
30_random-small28 | AC | 1 ms | 256 KB |
30_random-small29 | AC | 1 ms | 256 KB |
31_random-large00 | AC | 2 ms | 3328 KB |
31_random-large01 | AC | 2 ms | 3328 KB |
31_random-large02 | AC | 3 ms | 3456 KB |
31_random-large03 | AC | 2 ms | 3584 KB |
31_random-large04 | AC | 2 ms | 3456 KB |
40_boundary00 | WA | 1 ms | 256 KB |
40_boundary01 | AC | 2 ms | 1280 KB |