This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// oooo
/*
har chi delet mikhad bebar ~
gitar o ba khodet nabar! ~
;Amoo_Hasan;
*/
#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")
using namespace std;
typedef long long ll;
typedef long double ld;
#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
#define mak make_pair
//constexpr int PRI = 1000696969;
constexpr ll INF = 1e18, N = 1e6 + 10, MOD = 1e9 + 7;
int a[N];
bool mark[N];
int par[N];
int cnt[N];
vector<int> adj[N];
int main() {
ios :: sync_with_stdio(0), cin.tie(0); cout.tie(0);
int n; cin >>n;
for(int i = 1; i <= n; i++) cin >>a[i];
mark[1] = 1;
cnt[1] = a[1];
int cur = 0;
for(int i = 0; i < n - 1; i++) {
int u, v; cin >>u >>v;
if(mark[v]) swap(u, v);
mark[v] = 1;
cnt[v] = a[v];
par[v] = u;
vector<int> vc;
int x = u;
while(x) {
if(x > 1) {
if(cnt[x] != cnt[par[x]]) cur++;
}
vc.push_back(cnt[x]);
cnt[x] = cnt[v];
x = par[x];
}
ll ans = 0;
for(int j = 0; j < Sz(vc); j++)
for(int k = j + 1; k < Sz(vc); k++)
if(vc[j] < vc[k]) ans++;
cout<<ans <<endl;
}
if(cur >= 10000000) assert(0);
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... |