This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
if(shortest[a] == -1 || shortest[b] > 0){
assert(false);
}
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);
for(int x : group[a]){
group[b].push_back(x);
}
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |