#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, MAXV)
#define ffj For(j, 0, MAXV)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e endl//"\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
#define int short
const int MAXN=10000, MAXV = 100;
///500,000,000
int N, joke[MAXN];
bool rng[MAXV][MAXV], addst[MAXN], adden[MAXN];
vector<int> adj[MAXN], st[MAXN], en[MAXN];
void go(int at) {
for (int i: adj[at]) go(i);
ffa rng[i][j] = false;
for (int i: adj[at]) {
for (int j: st[i]) for (int k: en[i]) if ( k < joke[at] || joke[at] < j ) rng[j][k] = true;
st[i].clear(); en[i].clear();
}
rng[joke[at]][joke[at]] = true;
For (k, 0, MAXV-1) For (i, 0, k+1) For (j, k+1, MAXV) if (rng[i][k] && rng[k+1][j]) rng[i][j] = true;
//w<< at+1<<e; For (i, 0, 4) {For (j, 0, 4) w<< rng[i][j] << " "; w<<e;}
ffi addst[i] = adden[i] = false;
ffi For (j, i, MAXV) if (rng[i][j] && i <= joke[at] && joke[at] <= j) {
if (!addst[i]) {st[at].pb(i); addst[i] = true;}
if (!adden[j]) {en[at].pb(j); adden[j] = true;}
}
//w<< at+1<<e; w<< "st:"; for (int i: st[at]) w s i+1; w<<e; w<< "en:"; for (int i: en[at]) w s i+1; w<<e;
}
main() {
//ifstream cin("test.in");
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N;
For (i, 0, N) {cin >> joke[i]; joke[i]--;}
For (i, 1, N) {int a, b; cin >> a >> b; a--; b--; adj[a].pb(b);}
go(0);
w<< st[0].size()*en[0].size()<<e;
}
Compilation message
uzastopni.cpp:41:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
1016 KB |
Output is correct |
| 2 |
Correct |
16 ms |
1144 KB |
Output is correct |
| 3 |
Correct |
18 ms |
1016 KB |
Output is correct |
| 4 |
Correct |
18 ms |
1144 KB |
Output is correct |
| 5 |
Correct |
24 ms |
1144 KB |
Output is correct |
| 6 |
Correct |
23 ms |
1144 KB |
Output is correct |
| 7 |
Correct |
22 ms |
888 KB |
Output is correct |
| 8 |
Correct |
22 ms |
1016 KB |
Output is correct |
| 9 |
Correct |
23 ms |
1116 KB |
Output is correct |
| 10 |
Correct |
22 ms |
1016 KB |
Output is correct |
| 11 |
Execution timed out |
1071 ms |
1616 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1077 ms |
1628 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1078 ms |
1740 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1086 ms |
3456 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1072 ms |
3572 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1066 ms |
3688 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1075 ms |
1784 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1071 ms |
1656 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1070 ms |
1660 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1081 ms |
1656 KB |
Time limit exceeded |
