이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
//#pragma GCC optimize ("O2,unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
using namespace std;
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
#define pc __builtin_popcount
#define cl __builtin_clz
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define debug(x) cerr<<#x<<" : &"<<x<<"&\n"
#define wall() cerr<<'\n'<<"-------------------------------\n"
typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;
typedef pair<bool , pii> piii;
const ll
MX=5e3+5,
M=600,
MOD = 1e9+7,
inf = 1e9+20,
infl = 1e16,
LOG = 18,
A = 27,
del = 10067;
int n, fen[MX], p[MX], c[MX];
void add(int x, int N){
while(x<=N){
fen[x]++;
x+= x&(-x);
}
}
int ask(int x, int N){
int res=0;
while(x){
res+= fen[x];
x-= x&(-x);
}
return res;
}
int cntinv(vector<int>& vec){
int N = vec.size();
pii g[N+1]={};
int rnk[N+1]={};
FOR(i, 1, N) g[i] = pii(vec[i-1], i-1);
sort(g+1, g+N+1);
FOR(i, 1, N) rnk[g[i].S] = rnk[g[i-1].S]+(g[i].F>g[i-1].F);
memset(fen, 0, (N+1)*sizeof(int));
int res=0;
FOR(i, 0, N-1){
res+= i-ask(rnk[i], N);
add(rnk[i], N);
}
return res;
}
void solve(int v){
vector<int> vec;
for(int u=p[v]; u!=0; u=p[u]) vec.pb(c[u]);
reverse(vec.begin(), vec.end());
cout<<cntinv(vec)<<'\n';;
for(int u=p[v]; u!=0; u=p[u]) c[u]=c[v];
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
p[1] = 0;
FOR(i, 1, n) cin>>c[i];
FOR(i, 1, n-1){
int u, v;
cin>>u>>v;
p[v] = u;
solve(v);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |