#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define all(a) (a.begin(), a.end())
const int mod = 1e9 + 7;
const int N = 1e5;
int n, c[N+10];
vector<int> g[N+10], group[N+10];
int shortest[N+10];
int par[N+10];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1;i <= n; i++){
cin >> c[i];
shortest[i] = -1;
}
int q = n-1;
shortest[1] = 0;
par[1] = -1;
group[1].push_back(1);
while(q--){
int a, b; cin >> a >> b;
int cost = 0;
for(int s : group[a]){
if(shortest[s] == -1) continue;
for(int t : group[a]){
if(shortest[t] == -1) continue;
if(shortest[s] < shortest[t]){
cost+= (c[s] > c[t]);
}
}
}
g[a].push_back(b);
swap(group[b], group[a]);
group[b].push_back(b);
if(shortest[b] == -1 or shortest[b] > shortest[a]+1){
shortest[b] = shortest[a] + 1;
par[b] = a;
}
int parent = a;
while(parent != -1){
c[parent] = c[b];
parent = par[parent];
}
cout << cost << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
