| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 100431 | JPN20 | Construction of Highway (JOI18_construction) | C++17 | 0 ms | 0 KiB |
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;
vector<int>dat; int size_ = 1, rems = 1;
void inits(int sz) {
while (size_ <= sz) size_ *= 2;
dat.resize(size_ * 2, 0);
}
void update(int pos, int x) {
pos += size_;
dat[pos] = x;
while (pos >= 2) {
pos >>= 1;
dat[pos] = max(dat[pos * 2], dat[pos * 2 + 1]);
}
}
int query_(int l, int r, int a, int b, int u) {
if (l <= a && b <= r) return dat[u];
if (b <= l || r <= a) return -(1 << 30);
int s1 = query_(l, r, a, (a + b) >> 1, u * 2);
int s2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
return max(s1, s2);
}
int query(int l, int r) {
return query_(l, r, 0, size_, 1);
}
class BIT {
public:
vector<int>bit; int size1_;
void init(int sz) {
size1_ = sz + 2;
bit.resize(size1_ + 1, 0);
}
void add(int pos, int x) {
pos++;
while (pos <= size1_) {
bit[pos] += x; pos += (pos & -pos);
}
}
int sum(int pos) {
int s = 0; pos++;
while (pos >= 1) {
s += bit[pos]; pos -= (pos & -pos);
}
return s;
}
};
long long check_inversions(vector<pair<int, int>> vec) {
vector<int> A;
for (int i = 0; i < (int)vec.size(); i++) A.push_back(vec[i].first);
sort(A.begin(), A.end());
A.erase(unique(A.begin(), A.end()), A.end());
for (int i = 0; i < (int)vec.size(); i++) vec[i].first = lower_bound(A.begin(), A.end(), vec[i].first) - A.begin();
BIT Z; Z.init(A.size() + 1);
long long ans = 0;
for (int i = 0; i < (int)vec.size(); i++) {
ans += 1LL * vec[i].second * (Z.sum(A.size()) - Z.sum(vec[i].first));
Z.add(vec[i].first, vec[i].second);
}
return ans;
}
int N, C[1 << 17], A[1 << 17], B[1 << 17], dist[1 << 17], dp[1 << 17][20];
int cl[1 << 17], cr[1 << 17], cnts;
vector<int> X[1 << 17];
void dfs(int pos, int dep) {
cnts++; cl[pos] = cnts; dist[pos] = dep;
for (int i = 0; i < (int)X[pos].size(); i++) {
if (dist[X[pos][i]] != -1) continue;
dp[X[pos][i]][0] = pos;
dfs(X[pos][i], dep + 1);
}
cr[pos] = cnts;
}
int prevs(int pos, int x) {
for (int i = 19; i >= 0; i--) {
if (x >= (1 << i)) { x -= (1 << i); pos = dp[pos][i]; }
}
if (pos == 0) pos = 1;
return pos;
}
vector<pair<int, int>> get_inverse(int pos) {
vector<pair<int, int>> U;
while (true) {
// Binary Search.
int L = 0, R = dist[pos] + 1, M, maxn = (1 << 30);
int E = query(cl[pos], cr[pos] + 1);
for (int i = 0; i < 20; i++) {
M = (L + R) / 2;
int G = prevs(pos, M);
int P = query(cl[G], cr[G] + 1); //cout << "query(" << G << ") = " << P << endl;
if (E != P) { maxn = min(maxn, M); R = M; }
else { L = M; }
}
if (maxn == (1 << 30)) { U.push_back(make_pair(C[B[E]], dist[pos] + 1)); break; }
U.push_back(make_pair(C[B[E]], maxn));
pos = prevs(pos, maxn);
rem++;
assert(rem <= 500000);
}
reverse(U.begin(), U.end());
return U;
}
int main() {
scanf("%d", &N);
for (int i = 1; i <= N; i++) scanf("%d", &C[i]);
for (int i = 1; i <= N - 1; i++) {
scanf("%d%d", &A[i], &B[i]);
X[A[i]].push_back(B[i]);
X[B[i]].push_back(A[i]);
}
for (int i = 1; i <= N; i++) dist[i] = -1;
dfs(1, 0);
for (int i = 0; i < 19; i++) {
for (int j = 1; j <= N; j++) dp[j][i + 1] = dp[dp[j][i]][i];
}
//for (int i = 1; i <= N; i++) cout << i << ": cl = " << cl[i] << ", cr = " << cr[i] << endl;
inits(N + 2); update(cl[1], 0);
for (int i = 1; i <= N - 1; i++) {
vector<pair<int, int>> T = get_inverse(A[i]);
printf("%lld\n", check_inversions(T));
update(cl[B[i]], i);
}
return 0;
}