#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];
vector<int> adj[MAXN], st[MAXN], en[MAXN], dirfor[MAXV], dirbck[MAXV];
queue<int> nxt;
bool vis[MAXV];
void go(int at) {
for (int i: adj[at]) go(i);
ffi dirfor[i].clear(), dirbck[i].clear();
for (int i: adj[at]) for (int j: st[i]) for (int k: en[i]) if ( k < joke[at] || joke[at] < j ) dirfor[j].pb(k), dirbck[k].pb(j);
ffi vis[i] = false;
nxt.push(joke[at]);
vis[joke[at]] = true;
while (!nxt.empty()) {
int x = nxt.front(); nxt.pop();
en[at].pb(x);
if (x == MAXV-1) continue;
for (int i: dirfor[x+1]) if (!vis[i]) nxt.push(i);
}
ffi vis[i] = false;
nxt.push(joke[at]);
vis[joke[at]] = true;
while (!nxt.empty()) {
int x = nxt.front(); nxt.pop();
st[at].pb(x);
if (x == 0) continue;
for (int i: dirbck[x-1]) if (!vis[i]) nxt.push(i);
}
//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:49:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1016 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1016 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
1016 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
1016 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
1020 KB |
Output isn't correct |
| 6 |
Correct |
2 ms |
1016 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1144 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1016 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1016 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1016 KB |
Output is correct |
| 11 |
Incorrect |
10 ms |
1912 KB |
Output isn't correct |
| 12 |
Incorrect |
9 ms |
1912 KB |
Output isn't correct |
| 13 |
Incorrect |
11 ms |
1784 KB |
Output isn't correct |
| 14 |
Incorrect |
19 ms |
4344 KB |
Output isn't correct |
| 15 |
Correct |
19 ms |
4216 KB |
Output is correct |
| 16 |
Incorrect |
18 ms |
4344 KB |
Output isn't correct |
| 17 |
Incorrect |
9 ms |
1912 KB |
Output isn't correct |
| 18 |
Incorrect |
10 ms |
1832 KB |
Output isn't correct |
| 19 |
Correct |
8 ms |
1784 KB |
Output is correct |
| 20 |
Correct |
8 ms |
1784 KB |
Output is correct |
