QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #286428 | #7966. 采矿 | namelessgugugu | AC ✓ | 437ms | 136636kb | C++17 | 5.8kb | 2023-12-17 21:12:21 | 2023-12-17 21:12:22 |
Judging History
answer
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <vector>
#include <array>
#include <functional>
#define FILEIO(filename) (freopen(filename ".in", "r", stdin), freopen(filename ".out", "w", stdout))
typedef long long ll;
typedef unsigned long long ull;
using std::pair, std::vector, std::array;
const int N = 305;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, q, st, fa[N];
int spd[N][2];
vector<int> E[N];
int siz[N], dfn[N], rks[N], tt;
void dfs(int x)
{
siz[x] = 1, rks[dfn[x] = ++tt] = x;
for(int y : E[x])
dfs(y), siz[x] += siz[y];
return;
}
ll val[N][2][N];
ll f[N][N][N], g[N][N][N], h[N][N];
inline void chkmax(ll &x, ll y)
{
x = std::max(x, y);
return;
}
int pcnt;
void clear(void)
{
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= siz[E[i][0]]; ++j)
for (int k = 0; k <= siz[E[i][1]]; ++k)
f[i][j][k] = -inf;
for (int i = 1; i <= n;++i)
for (int j = 0; j <= n;++j)
h[i][j] = -inf;
return;
}
void move(void)
{
for (int i = 1; i <= n;++i)
for (int j = 0; j <= siz[E[i][0]];++j)
for (int k = 0; k <= siz[E[i][1]];++k)
g[i][j][k] = f[i][j][k];
return;
}
void trans(int ty)
{
if(ty == 1)
{
for (int i = 2; i <= n; ++i)
for (int j = 0; j <= siz[E[i][0]]; ++j)
for (int k = 0; k <= siz[E[i][1]]; ++k)
if(g[i][j][k] >= 0 && pcnt - j - k < n - siz[i])
chkmax(h[i][j + k], g[i][j][k]);
for (int i = n; i >= 1;--i)
{
int x = rks[i];
for (int j = 0; j <= siz[E[x][0]];++j)
for (int k = 0; k <= siz[E[x][1]];++k)
if(j + k <= pcnt && pcnt - j - k <= n - siz[x])
{
if (h[E[x][0]][j] >= 0 && E[x][0])
chkmax(f[x][j][k], h[E[x][0]][j]);
if (h[E[x][1]][k] >= 0 && E[x][1])
chkmax(f[x][j][k], h[E[x][1]][k]);
if (f[x][j][k] >= 0 && pcnt - j - k < n - siz[x])
chkmax(h[x][j + k], f[x][j][k]);
}
}
}
else if(ty == 2)
{
for (int i = 1; i <= n;++i)
for (int j = 0; j <= siz[E[i][0]];++j)
for (int k = 0; k <= siz[E[i][1]];++k)
if(g[i][j][k] >= 0)
{
if(j < siz[E[i][0]])
chkmax(h[E[i][0]][j], g[i][j][k]);
if(k < siz[E[i][1]])
chkmax(h[E[i][1]][k], g[i][j][k]);
}
for (int i = 1; i <= n;++i)
{
int x = rks[i];
for (int j = 0; j <= siz[E[x][0]]; ++j)
for (int k = 0; k <= siz[E[x][1]]; ++k)
if (j + k <= pcnt && pcnt - j - k <= n - siz[x])
{
if(h[x][j + k] >= 0)
chkmax(f[x][j][k], h[x][j + k]);
if(f[x][j][k] >= 0)
{
if (j < siz[E[x][0]])
chkmax(h[E[x][0]][j], f[x][j][k]);
if (k < siz[E[x][1]])
chkmax(h[E[x][1]][k], f[x][j][k]);
}
}
}
}
else if(ty == 3)
{
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= siz[E[i][0]]; ++j)
for (int k = 0; k <= siz[E[i][1]]; ++k)
if(g[i][j][k] >= 0 && pcnt - j - k < n - siz[i])
f[i][j][k] = g[i][j][k];
++pcnt;
}
else if(ty == 4)
{
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= siz[E[i][0]]; ++j)
for (int k = 0; k <= siz[E[i][1]]; ++k)
if (g[i][j][k] >= 0 && pcnt - j - k > 0)
f[i][j][k] = g[i][j][k];
--pcnt;
}
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= siz[E[i][0]]; ++j)
for (int k = 0; k <= siz[E[i][1]]; ++k)
if (f[i][j][k] >= 0)
f[i][j][k] += val[E[i][0]][0][j] + val[E[i][1]][0][k] + val[i][1][pcnt - j - k] + spd[i][0];
return;
}
int main(void)
{
scanf("%d%d%d", &n, &q, &st);
for (int i = 2; i <= n;++i)
scanf("%d", fa + i), E[fa[i]].push_back(i);
for (int o = 0; o < 2;++o)
for (int i = 2; i <= n;++i)
scanf("%d", spd[i] + o);
dfs(1);
for (int i = 1; i <= n;++i)
while(E[i].size() < 2u)
E[i].push_back(0);
for (int i = 1; i <= n; ++i)
{
vector<int> vec[2];
for (int j = 1; j <= n; ++j)
if (dfn[j] >= dfn[i] && dfn[j] < dfn[i] + siz[i])
vec[0].push_back(spd[j][1]);
else
vec[1].push_back(spd[j][1]);
std::sort(vec[0].begin(), vec[0].end(), std::greater<int>());
std::sort(vec[1].begin(), vec[1].end(), std::greater<int>());
for (int j = 1; j <= siz[i]; ++j)
val[i][0][j] = val[i][0][j - 1] + vec[0][j - 1];
for (int j = 1; j <= n - siz[i]; ++j)
val[i][1][j] = val[i][1][j - 1] + vec[1][j - 1];
}
clear();
f[st][0][0] = 0;
for (int op = 1, ty; op <= q; ++op)
{
move(), clear();
scanf("%d", &ty);
trans(ty);
}
ll ans = -inf;
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= siz[E[i][0]]; ++j)
for (int k = 0; k <= siz[E[i][1]]; ++k)
chkmax(ans, f[i][j][k]);
if(ans < 0)
puts("No solution.");
else
printf("%lld\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 114ms
memory: 48156kb
input:
300 600 175 1 2 1 4 4 2 7 8 9 8 3 5 12 10 6 6 13 15 9 11 11 13 15 22 14 26 27 12 5 16 10 24 23 16 33 34 21 22 37 39 17 39 40 20 36 28 40 33 48 29 26 46 46 18 37 32 20 38 54 45 19 30 52 27 18 60 41 57 30 50 48 47 65 17 35 14 55 24 78 80 71 81 28 3 21 19 63 35 75 75 73 92 89 36 81 50 34 93 85 43 42 78...
output:
4588927051034
result:
ok single line: '4588927051034'
Test #2:
score: 0
Accepted
time: 118ms
memory: 51868kb
input:
300 600 286 1 1 3 3 5 6 6 7 7 9 2 2 9 10 5 13 11 12 8 15 20 22 11 15 21 16 4 26 19 20 25 27 10 23 13 12 32 32 8 26 18 19 28 42 4 46 41 37 23 43 30 25 34 47 49 22 40 48 28 45 16 35 35 63 55 33 44 61 21 56 61 59 63 65 73 47 42 51 62 76 48 59 39 66 58 77 57 73 68 27 29 53 85 83 56 41 60 69 74 58 100 10...
output:
40349159313289
result:
ok single line: '40349159313289'
Test #3:
score: 0
Accepted
time: 437ms
memory: 135672kb
input:
301 600 153 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...
output:
44810792039851
result:
ok single line: '44810792039851'
Test #4:
score: 0
Accepted
time: 178ms
memory: 73640kb
input:
300 600 264 1 1 2 2 3 6 6 7 9 10 10 12 5 11 15 12 11 14 16 14 17 17 16 21 25 19 27 28 26 28 24 29 33 31 35 34 31 30 32 39 33 39 37 43 44 46 42 46 43 49 45 45 47 48 51 47 56 57 54 57 59 53 58 56 58 59 61 60 68 65 67 68 70 69 67 69 70 73 72 80 76 76 82 78 77 77 87 87 82 90 85 85 91 86 95 93 96 96 91 9...
output:
52315813623226
result:
ok single line: '52315813623226'
Test #5:
score: 0
Accepted
time: 182ms
memory: 70724kb
input:
300 600 33 1 1 2 4 4 2 5 5 9 9 8 11 10 12 13 13 15 11 18 19 18 16 19 22 17 22 21 23 28 25 29 27 29 34 28 30 31 36 38 34 39 39 35 44 36 42 38 45 41 45 43 52 44 52 51 48 55 56 55 56 60 57 54 60 58 66 59 63 63 61 68 67 68 65 72 71 74 76 72 80 73 74 83 81 82 81 79 87 86 85 91 86 88 88 94 89 90 94 98 97 ...
output:
48722943497148
result:
ok single line: '48722943497148'
Test #6:
score: 0
Accepted
time: 166ms
memory: 71704kb
input:
300 600 42 1 1 3 4 2 2 5 8 8 9 6 9 11 13 11 12 15 12 10 19 15 19 21 18 16 25 18 21 28 28 23 29 27 34 26 27 31 33 30 32 37 34 39 43 42 45 39 40 40 45 51 50 50 51 52 52 54 58 55 57 59 60 54 62 65 66 66 67 60 63 62 63 73 73 68 76 76 71 71 77 81 78 82 79 84 79 84 83 87 87 85 91 92 89 94 93 90 95 99 95 9...
output:
55427849622319
result:
ok single line: '55427849622319'
Test #7:
score: 0
Accepted
time: 176ms
memory: 74440kb
input:
300 600 137 1 2 1 3 2 6 7 6 4 8 11 5 11 5 13 12 10 10 12 17 13 18 22 18 21 20 20 23 23 27 27 29 25 29 33 35 36 31 33 35 40 40 43 44 39 43 41 46 42 46 49 44 53 52 55 54 51 55 51 59 56 61 54 62 61 59 64 62 60 68 67 63 65 73 72 73 72 75 74 79 77 80 78 76 77 83 78 80 88 89 86 90 89 91 90 93 92 97 95 95 ...
output:
53287628221118
result:
ok single line: '53287628221118'
Test #8:
score: 0
Accepted
time: 192ms
memory: 80856kb
input:
300 600 70 1 1 2 2 3 3 5 6 9 8 9 10 13 8 6 12 16 12 17 16 20 20 21 23 23 21 22 27 22 28 25 31 25 33 34 33 37 38 34 35 35 38 36 43 39 39 45 40 41 42 43 44 52 54 47 50 57 53 51 56 56 53 60 63 61 65 58 66 61 68 62 65 69 73 72 68 72 78 76 79 74 76 82 81 84 77 84 88 85 85 82 91 86 92 89 92 91 95 98 99 96...
output:
52245066034805
result:
ok single line: '52245066034805'
Test #9:
score: 0
Accepted
time: 163ms
memory: 71220kb
input:
300 600 56 1 2 2 4 3 6 1 7 7 6 5 11 8 12 12 10 9 14 13 11 14 13 18 21 20 25 18 21 20 27 24 32 32 33 29 30 28 30 37 40 33 36 34 38 41 38 47 48 44 43 48 51 53 50 49 56 52 56 55 52 57 54 60 63 61 60 61 68 65 70 63 66 70 69 67 72 77 77 72 73 80 78 81 81 80 78 82 88 88 89 90 89 90 91 86 87 97 91 93 97 94...
output:
54169471106772
result:
ok single line: '54169471106772'
Test #10:
score: 0
Accepted
time: 176ms
memory: 69432kb
input:
300 600 105 1 1 3 3 2 6 4 2 8 5 9 6 10 14 7 12 13 9 17 14 12 20 21 19 22 22 24 27 23 30 28 29 32 34 32 33 30 33 35 31 38 38 35 43 36 39 44 44 43 46 50 50 45 53 48 52 56 57 52 54 53 59 55 59 64 62 66 60 60 66 70 63 70 71 72 74 77 78 72 76 75 81 80 82 80 85 79 79 89 89 83 90 91 94 86 88 97 95 95 94 10...
output:
50990422314888
result:
ok single line: '50990422314888'
Test #11:
score: 0
Accepted
time: 183ms
memory: 75592kb
input:
300 600 99 1 2 3 1 3 5 6 6 2 8 11 10 9 13 10 14 13 16 17 17 19 19 20 15 21 18 18 27 29 28 23 29 30 34 31 35 32 31 37 40 34 40 42 42 39 38 47 48 43 47 51 46 49 50 51 48 49 58 50 54 52 62 60 57 63 63 64 68 62 66 70 67 69 71 66 74 71 76 76 77 81 75 81 77 85 84 82 85 89 86 82 87 92 94 86 96 90 97 90 96 ...
output:
50233132966129
result:
ok single line: '50233132966129'
Test #12:
score: 0
Accepted
time: 121ms
memory: 54444kb
input:
300 600 57 1 1 3 4 4 5 7 8 6 8 9 10 3 5 12 11 13 16 12 15 19 11 17 17 19 25 14 2 29 10 9 32 28 29 32 33 34 7 16 36 25 27 38 38 6 26 18 42 27 49 36 20 28 43 20 14 37 18 34 24 53 2 31 53 31 33 54 40 30 41 57 44 64 46 42 71 60 51 59 45 49 21 54 47 47 75 69 45 24 23 80 87 86 75 95 92 70 48 55 95 56 90 6...
output:
4351680767374
result:
ok single line: '4351680767374'
Test #13:
score: 0
Accepted
time: 164ms
memory: 52668kb
input:
300 600 111 1 2 1 4 3 6 5 8 7 5 10 12 7 11 6 14 17 12 13 13 20 14 21 23 17 18 23 20 29 28 22 30 28 34 34 31 35 29 31 32 36 37 40 37 39 43 43 41 40 49 44 46 44 48 49 48 53 55 53 51 52 62 59 55 63 66 60 65 65 70 67 69 66 71 73 67 73 77 76 72 72 80 77 83 82 84 84 82 88 90 83 87 88 87 93 96 92 93 98 98 ...
output:
50231080085638
result:
ok single line: '50231080085638'
Test #14:
score: 0
Accepted
time: 164ms
memory: 71796kb
input:
300 600 202 1 1 3 4 3 2 7 6 2 10 10 11 5 8 7 12 8 11 18 17 18 17 20 22 20 21 24 26 27 23 28 31 28 30 26 30 29 32 38 36 35 38 40 36 40 46 43 45 45 46 47 49 48 50 52 51 56 53 50 56 60 57 58 64 65 64 59 60 68 63 70 63 73 73 75 76 71 75 78 77 81 76 83 84 78 85 81 86 82 82 83 92 90 94 90 96 91 93 94 91 9...
output:
47868585292289
result:
ok single line: '47868585292289'
Test #15:
score: 0
Accepted
time: 96ms
memory: 33872kb
input:
301 600 150 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19 21 21 23 23 25 25 27 27 29 29 31 31 33 33 35 35 37 37 39 39 41 41 43 43 45 45 47 47 49 49 51 51 53 53 55 55 57 57 59 59 61 61 63 63 65 65 67 67 69 69 71 71 73 73 75 75 77 77 79 79 81 81 83 83 85 85 87 87 89 89 91 91 93 93 95 95 97 97 99 9...
output:
1557184330900
result:
ok single line: '1557184330900'
Test #16:
score: 0
Accepted
time: 144ms
memory: 42064kb
input:
300 600 191 1 2 3 2 4 4 6 6 8 9 3 7 13 7 13 11 14 12 15 15 21 16 14 22 25 22 24 23 21 26 28 27 28 33 30 33 32 36 30 31 32 35 37 43 40 45 39 40 41 41 48 46 46 54 53 55 57 49 50 59 60 59 61 57 61 65 66 64 63 63 64 66 71 73 74 69 71 74 76 79 76 79 81 78 85 86 83 87 83 87 86 84 90 92 91 96 90 93 92 91 9...
output:
No solution.
result:
ok single line: 'No solution.'
Test #17:
score: 0
Accepted
time: 160ms
memory: 76040kb
input:
300 600 189 1 2 2 4 4 1 5 5 8 7 11 12 12 7 15 15 8 18 10 13 21 20 22 16 21 22 20 19 24 23 30 28 29 34 29 30 37 38 38 36 32 42 34 35 41 40 39 40 47 48 45 49 48 53 49 47 55 57 53 51 56 54 59 64 56 59 64 65 62 62 66 71 70 66 70 67 69 73 77 77 76 73 80 84 81 79 87 79 83 84 85 83 87 94 94 93 88 97 90 92 ...
output:
No solution.
result:
ok single line: 'No solution.'
Test #18:
score: 0
Accepted
time: 87ms
memory: 87708kb
input:
300 600 271 1 2 2 4 4 5 1 8 9 5 11 3 12 7 11 7 16 9 19 19 16 8 3 24 25 25 27 14 10 15 17 15 32 20 29 26 26 28 23 33 23 28 41 35 27 44 32 47 17 44 6 50 52 35 54 10 45 55 43 52 13 21 46 42 20 42 47 60 64 67 39 21 57 56 63 55 71 18 22 54 43 57 34 56 36 51 59 68 53 59 74 34 76 69 94 48 13 41 53 64 12 18...
output:
No solution.
result:
ok single line: 'No solution.'
Test #19:
score: 0
Accepted
time: 100ms
memory: 78776kb
input:
300 600 64 1 1 3 3 2 5 5 8 8 9 6 12 4 12 15 14 16 16 14 2 13 18 6 15 7 13 18 22 20 10 24 31 20 26 26 31 32 33 37 24 36 37 10 27 33 7 42 44 22 38 38 9 49 32 55 53 21 19 57 35 43 55 51 21 34 62 17 43 48 68 53 47 65 69 50 72 70 47 25 40 67 50 39 77 45 60 36 81 29 65 58 41 41 63 72 60 83 56 97 19 68 90 ...
output:
No solution.
result:
ok single line: 'No solution.'
Test #20:
score: 0
Accepted
time: 78ms
memory: 90028kb
input:
300 600 170 1 2 3 2 1 6 7 4 7 4 10 9 5 10 11 9 5 17 17 16 3 19 20 8 13 8 20 12 19 22 28 28 29 14 22 11 29 25 14 6 13 40 36 35 45 18 37 12 47 31 15 26 25 41 49 26 31 53 53 34 21 45 23 42 58 47 61 66 59 39 61 66 44 21 48 75 50 27 77 48 77 56 60 75 63 62 86 84 67 71 38 51 81 30 37 85 89 80 87 36 78 52 ...
output:
No solution.
result:
ok single line: 'No solution.'
Test #21:
score: 0
Accepted
time: 120ms
memory: 100220kb
input:
300 600 214 1 1 3 3 5 5 4 4 9 10 7 9 13 11 7 8 15 10 16 11 18 17 22 23 12 18 16 25 23 24 12 15 24 14 21 31 36 21 17 39 39 36 30 20 32 26 45 38 46 8 49 22 30 28 33 49 50 58 27 44 32 46 58 44 37 48 38 28 43 13 62 66 31 14 35 63 74 34 68 25 42 26 76 76 19 41 85 56 29 78 63 61 82 59 64 6 62 65 97 43 51 ...
output:
4485712836520
result:
ok single line: '4485712836520'
Test #22:
score: 0
Accepted
time: 2ms
memory: 16180kb
input:
6 3 2 1 2 3 3 2 45 38 27 44 79 5 3 5 5 9 1 2 3
output:
163
result:
ok single line: '163'
Test #23:
score: 0
Accepted
time: 111ms
memory: 122508kb
input:
300 600 296 1 1 3 4 4 5 7 7 6 3 5 12 12 13 2 10 13 2 8 20 15 21 16 16 24 24 8 26 18 22 18 27 21 34 10 34 20 38 25 38 28 36 28 22 6 40 40 42 15 44 44 29 29 9 41 50 57 43 50 57 42 32 62 46 14 60 56 9 41 30 71 60 63 54 48 65 73 74 14 27 63 72 25 66 56 71 43 23 32 70 83 48 88 49 26 47 85 53 39 23 45 98 ...
output:
4411111707253
result:
ok single line: '4411111707253'
Test #24:
score: 0
Accepted
time: 121ms
memory: 124000kb
input:
300 600 110 1 1 2 3 2 4 6 3 6 10 7 7 13 4 8 9 11 14 15 9 15 19 13 5 21 5 8 11 23 18 10 26 22 23 16 30 34 20 20 22 34 36 33 31 16 21 40 19 17 43 31 35 14 35 12 12 30 26 50 51 59 59 56 43 44 55 18 48 46 29 62 28 28 44 50 25 65 71 74 77 61 55 25 39 80 84 71 74 62 80 63 48 67 17 69 76 87 38 82 83 27 51 ...
output:
4479248027267
result:
ok single line: '4479248027267'
Test #25:
score: 0
Accepted
time: 118ms
memory: 114136kb
input:
300 600 254 1 2 1 3 2 6 3 7 8 10 9 5 4 12 5 16 6 13 13 4 18 10 11 14 8 23 7 16 22 18 15 26 25 31 19 11 29 29 35 20 41 42 14 25 23 35 33 24 36 33 27 15 40 48 41 39 39 46 19 12 36 51 34 37 61 58 22 58 42 64 32 20 28 9 72 60 76 49 46 70 47 61 69 80 45 69 76 79 44 90 86 34 77 60 71 48 64 66 43 86 92 53 ...
output:
4532069466798
result:
ok single line: '4532069466798'
Test #26:
score: 0
Accepted
time: 119ms
memory: 126440kb
input:
300 600 274 1 1 2 4 3 4 2 7 9 7 11 9 10 3 8 16 5 17 16 10 5 14 23 22 24 25 24 27 28 11 8 22 27 6 12 18 20 12 6 23 15 41 26 34 29 20 37 14 18 41 35 37 31 43 29 32 15 26 47 42 19 32 17 35 21 30 65 68 36 28 49 13 70 58 49 65 75 55 61 47 54 55 82 46 58 60 68 73 39 64 25 75 50 31 45 50 66 97 73 53 82 94 ...
output:
37149511717824
result:
ok single line: '37149511717824'
Test #27:
score: 0
Accepted
time: 118ms
memory: 136636kb
input:
300 600 262 1 2 1 4 5 5 3 7 7 6 11 8 3 11 2 16 9 17 8 19 12 13 20 14 9 6 4 16 17 24 29 30 32 15 23 18 23 19 33 21 31 12 36 29 44 36 41 45 31 18 33 25 35 39 46 50 46 52 35 38 52 61 32 39 59 27 30 57 63 43 56 28 45 50 63 74 64 61 71 79 56 60 69 27 13 20 87 28 76 10 82 75 15 21 24 70 43 94 58 75 69 55 ...
output:
38295501087283
result:
ok single line: '38295501087283'