#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[3][V], rt[3][V], clr;
int n, a[N];
void clear(int tp){
for (int i = 0; i < V; i++){
lf[tp][i] = clr;
rt[tp][i] = clr;
}
}
void dfs(int v, int p){
int lst = 0;
for (int u : g[v]){
if (u == p) continue;
dfs(u, v);
}
clear(0);
lf[0][a[v]][a[v]] = 1;
rt[0][a[v]][a[v]] = 1;
for (int u : g[v]){
if (u == p) continue;
// cerr << lf[lst][1][3] << '\n';
lst ^= 1;
clear(lst);
for (int l = 1; l < V; l++)
for (int r = l; r < V; r++)
if (f[u][l][r] && !lf[lst ^ 1][l][r]){
lf[lst][l][r] = 1;
if (r + 1 < V)
lf[lst][l] |= (lf[lst ^ 1][r + 1]);
rt[lst][r][l] = 1;
if (l > 1)
rt[lst][r] |= (rt[lst ^ 1][l - 1]);
}
clear(2);
for (int r = 2; r < V; r++)
for (int l = r - 1; l > 0; l--) {
if (rt[lst][r - 1][l] || lf[lst][l][r - 1])
lf[2][l] |= lf[lst ^ 1][r];
if (lf[lst ^ 1][l][r])
lf[2][l] |= lf[lst][r];
//right too
}
for (int l = 2; l < V; l++)
for (int r = l; r < V; r++){
if (rt[lst][r][l] || lf[lst][l][r])
rt[2][r] |= rt[lst ^ 1][l - 1];
if (rt[lst ^ 1][l][r])
rt[2][r] |= rt[lst][l - 1];
}
for (int l = 1; l < V; l++)
for (int r = l; r < V; r++){
bool res = bool(lf[2][l][r] || rt[2][r][l] || lf[lst ^ 1][l][r] || rt[lst ^ 1][r][l] || lf[lst][l][r] || rt[lst][r][l]);
lf[lst][l][r] = res;
rt[lst][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][l][r];
// if (v == 1) {
// cerr << "ADSGDA " << f[v][1][3] << '\n';
// cerr << "ADSGDA " << f[v][2][3] << '\n';
// cerr << "ADSGDA " << f[v][3][3] << '\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]) {
// cerr << l << " " << r << '\n';
ans++;
}
cout << ans;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
640 KB |
Output is correct |
| 2 |
Correct |
5 ms |
640 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
768 KB |
Output isn't correct |
| 4 |
Incorrect |
5 ms |
768 KB |
Output isn't correct |
| 5 |
Incorrect |
7 ms |
768 KB |
Output isn't correct |
| 6 |
Correct |
7 ms |
768 KB |
Output is correct |
| 7 |
Correct |
7 ms |
768 KB |
Output is correct |
| 8 |
Correct |
7 ms |
768 KB |
Output is correct |
| 9 |
Correct |
8 ms |
768 KB |
Output is correct |
| 10 |
Correct |
7 ms |
768 KB |
Output is correct |
| 11 |
Execution timed out |
610 ms |
16892 KB |
Time limit exceeded |
| 12 |
Execution timed out |
592 ms |
16760 KB |
Time limit exceeded |
| 13 |
Execution timed out |
584 ms |
16832 KB |
Time limit exceeded |
| 14 |
Execution timed out |
632 ms |
18876 KB |
Time limit exceeded |
| 15 |
Execution timed out |
626 ms |
18808 KB |
Time limit exceeded |
| 16 |
Execution timed out |
623 ms |
18680 KB |
Time limit exceeded |
| 17 |
Execution timed out |
599 ms |
16760 KB |
Time limit exceeded |
| 18 |
Execution timed out |
589 ms |
16884 KB |
Time limit exceeded |
| 19 |
Execution timed out |
597 ms |
16760 KB |
Time limit exceeded |
| 20 |
Execution timed out |
607 ms |
16888 KB |
Time limit exceeded |
