#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#define sz(x) ((int)x.size())
#define i2 array<int,2>
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 10010;
const int V = 101;
const int C = 22;
const int md = 10007;
vector<int> g[N];
bitset<V> f[N][V], lf[2][N][V], rt[2][N][V], clr;
int n, a[N];
void clear(int tp, int v){
for (int i = 0; i < V; i++){
lf[tp][v][i] = clr;
rt[tp][v][i] = clr;
}
}
void dfs(int v, int p){
// f[v][a[v]][a[v]] = 1;
// cerr << v << '\n';
clear(0, v);
lf[0][v][a[v]][a[v]] = 1;
rt[0][v][a[v]][a[v]] = 1;
int lst = 0;
for (int u : g[v]){
if (u == p) continue;
dfs(u, v);
lst ^= 1;
clear(lst, v);
for (int l = 1; l < V; l++)
for (int r = l; r < V; r++)
if (f[u][l][r]){
lf[lst][v][l][r] = 1;
if (r + 1 < V)
lf[lst][v][l] |= (lf[lst ^ 1][v][r + 1]);
rt[lst][v][r][l] = 1;
if (l > 1) {
rt[lst][v][r] |= (rt[lst ^ 1][v][l - 1]);
// if (v == 2)
// cerr << rt[lst ^ 1][l - 1][l - 1] << '\n';
}
}
for (int l = 1; l < V; l++)
for (int r = l; r < V; r++){
bool res = bool(lf[lst][v][l][r] || rt[lst][v][r][l] || lf[lst ^ 1][v][l][r] || rt[lst ^ 1][v][r][l]);
lf[lst][v][l][r] = res;
rt[lst][v][r][l] = res;
}
}
for (int l = 1; l < V; l++)
for (int r = l; r < V; r++)
if (l <= a[v] && r >= a[v])
f[v][l][r] = lf[lst][v][l][r];
// if (v == 2) {
// cerr << "DGDG " << f[v][3][3] << '\n';
// cerr << "DGDG " << f[v][3][4] << '\n';
// }
}
int main() {
#ifdef _LOCAL
freopen("in.txt","r",stdin); // freopen("output.txt","w",stdout);
#else
// freopen("mining.in","r",stdin); freopen("mining.out","w",stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
#endif
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 1; i < n; i++){
int x, y; cin >> x >> y;
x--; y--;
g[x].PB(y);
g[y].PB(x);
}
dfs(0, -1);
int ans = 0;
for (int l = 1; l < V; l++)
for (int r = l; r < V; r++)
if (f[0][l][r])
ans++;
cout << ans;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
1024 KB |
Output isn't correct |
| 2 |
Correct |
4 ms |
1152 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
1152 KB |
Output isn't correct |
| 4 |
Incorrect |
3 ms |
1152 KB |
Output isn't correct |
| 5 |
Incorrect |
4 ms |
1408 KB |
Output isn't correct |
| 6 |
Correct |
4 ms |
1280 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1280 KB |
Output is correct |
| 8 |
Correct |
4 ms |
1280 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1280 KB |
Output is correct |
| 10 |
Correct |
4 ms |
1280 KB |
Output is correct |
| 11 |
Runtime error |
223 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
217 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
212 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
265 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
246 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
256 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
219 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
221 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 19 |
Runtime error |
355 ms |
48888 KB |
Memory limit exceeded |
| 20 |
Runtime error |
338 ms |
48888 KB |
Memory limit exceeded |
