QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#810523 | #8647. JOI Tour | topfloorboss | 0 | 4ms | 4712kb | C++20 | 11.0kb | 2024-12-12 00:25:46 | 2024-12-12 00:25:52 |
answer
#include "joitour.h"
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <bitset>
#include <iterator>
#include <iomanip>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <random>
#include <cassert>
using namespace std;
struct Fenwick {
int n;
vector<long long> tree;
Fenwick() {}
void build(int x) {
n = x;
tree.resize(n + 1);
}
long long get_sum(int ind){
long long ans = 0;
for (int i = ind; i >= 0; i = (i & (i + 1)) - 1){
ans += tree[i];
}
return ans;
}
void upd(int ind, long long x){
for (int i = ind; i < n; i = (i | (i + 1))){
tree[i] += x;
}
}
long long su(int l, int r){
return get_sum(r) - get_sum(l-1);
}
};
struct Fenwick2 {
int n;
vector<long long> tree;
Fenwick2() {}
void build(int x) {
n = x;
tree.resize(n + 3);
}
long long get(int ind) {
long long ans = 0;
for (int i = ind; i >= 0; i = (i & (i + 1)) - 1){
ans += tree[i];
}
return ans;
}
void upd(int ind, long long x) {
for (int i = ind; i < n; i = (i | (i + 1))){
tree[i] += x;
}
}
void upd(int l, int r, int x) {
upd(l, x);
upd(r + 1, -x);
}
};
vector<vector<int>> g;
vector<int> col;
long long anss = 0;
struct HLD {
vector<vector<int>> gr;
map<int, int> gt;
vector<int> ord, tin, tout, backord, up, sz, pr, uppest, c;
vector<long long> ct01, ct21, ct0, ct2;
vector<Fenwick> lol;
Fenwick2 lol1;
int timer = 1;
long long ans = 0, tans = 0;
void dfssz(int v, int p) {
if (p != -1) {
pr[v] = p;
for (int i = 0; i < (int)gr[v].size() - 1; ++i) {
if (gr[v][i] == p) {
swap(gr[v][i], gr[v][i + 1]);
}
}
if (gr[v].size()) gr[v].pop_back();
}
if (p == -1) {
for (auto e : gr[v]) {
uppest[e] = e;
}
} else {
for (auto e : gr[v]) {
uppest[e] = uppest[v];
}
}
sz[v] = 1;
tin[v] = timer++;
for (auto e : gr[v]) {
dfssz(e, v);
ct0[v] += ct0[e];
ct2[v] += ct2[e];
ct01[v] += ct01[e];
ct21[v] += ct21[e];
sz[v] += sz[e];
}
tout[v] = timer++;
if (c[v] == 0) {
ct0[v]++;
}
if (c[v] == 2) {
ct2[v]++;
}
if (c[v] == 1) {
ct01[v] += ct0[v];
ct21[v] += ct2[v];
}
}
void dfs(int v) {
backord[v] = ord.size();
ord.push_back(v);
if (gr[v].size() == 0) return;
for (auto &e : gr[v]) {
up[e] = e;
if (sz[e] > sz[gr[v][0]]) {
swap(e, gr[v][0]);
}
}
up[gr[v][0]] = up[v];
for (auto e : gr[v]) {
dfs(e);
}
}
HLD(){}
void upd(int v, int x) {
lol1.upd(backord[v], backord[v] + sz[v] - 1, x);
}
long long get1s(int v) {
return lol1.get(backord[v]);
}
long long get0s(int v) {
return lol[0].su(backord[v], backord[v] + sz[v] - 1);
}
long long get2s(int v) {
return lol[2].su(backord[v], backord[v] + sz[v] - 1);
}
void build(vector<int> kek) {
int n = (int)kek.size();
gr.resize(n);
for (int i = 0; i < n; ++i) gt[kek[i]] = i;
c.resize(n);
for (int i = 0; i < n; ++i) {
c[i] = col[kek[i]];
for (auto e : g[kek[i]]) {
if (gt.find(e) != gt.end()) {
gr[i].push_back(gt[e]);
}
}
}
uppest.resize(n);
tin.resize(n);
tout.resize(n);
backord.resize(n);
up.resize(n);
sz.resize(n);
pr.resize(n);
ct0.resize(n);
ct2.resize(n);
ct01.resize(n);
ct21.resize(n);
dfssz(0, -1);
dfs(0);
lol.resize(3);
lol1.build(n);
for (int i = 0; i < 3; ++i) {
if (i == 1) continue;
lol[i].build(n);
}
for (int i = 0; i < n; ++i) {
if (c[ord[i]] == 1) continue;
lol[c[ord[i]]].upd(i, 1);
}
for (int i = 0; i < n; ++i) {
if (c[ord[i]] == 1) {
upd(ord[i], 1);
}
}
for (auto e : gr[0]) {
ans += ct01[e] * (ct2[0] - ct2[e]);
ans += ct21[e] * (ct0[0] - ct0[e]);
int T = ct2[0] - ct2[e];
if (c[0] == 2) T--;
if (c[0] == 1) {
ans += ct0[e] * (ct2[0] - ct2[e]);
}
// tans += ct0[e] * T;
}
}
int get01(int v) {
if (c[0] == 1) return ct01[0] - ct01[v] - ct0[0];
return ct01[0] - ct01[v];
}
int get21(int v) {
if (c[0] == 1) return ct21[0] - ct21[v] - ct2[0];
return ct21[0] - ct21[v];
}
void kek1(int v, int col) {
v = gt[v];
if (v == 0) {
if (c[v] == 2) {
ans -= ct01[0];
ct2[v]--;
lol[2].upd(backord[v], -1);
}
if (c[v] == 0) {
ans -= ct21[0];
ct0[v]--;
lol[0].upd(backord[v], -1);
}
if (c[v] == 1) {
ct01[v] -= ct0[v];
ct21[v] -= ct2[v];
upd(0, -1);
}
c[v] = col;
if (c[v] == 2) {
ans += ct01[0];
ct2[v]++;
lol[2].upd(backord[v], 1);
}
if (c[v] == 0) {
ans += ct21[0];
ct0[v]++;
lol[0].upd(backord[v], 1);
}
if (c[v] == 1) {
ct01[v] += ct0[v];
ct21[v] += ct2[v];
upd(0, 1);
}
return;
}
int t = uppest[v];
int e = t;
if (c[v] == 0) {
int TT = get1s(v);
if (c[0] == 1) TT--;
ans -= TT * (ct2[0] - ct2[t]);
ans -= get21(t);
ct0[t]--;
ct01[t] -= get1s(v);
if (c[0] == 1) ct01[t]++;
ct0[0]--;
ct01[0] -= get1s(v);
lol[0].upd(backord[v], -1);
int T = ct2[0] - ct2[t];
if (c[0] == 2) T--;
tans -= T;
}
if (c[v] == 1) {
ans -= get0s(v) * (ct2[0] - ct2[t]);
ans -= get2s(v) * (ct0[0] - ct0[t]);
ct01[0] -= get0s(v);
ct21[0] -= get2s(v);
upd(v, -1);
}
if (c[v] == 2) {
int TT = get1s(v);
if (c[0] == 1) TT--;
ans -= TT * (ct0[0] - ct0[t]);
ans -= get01(t);
// cout << get01(t) << ' ' << get1s(v) * (ct0[0] - ct0[t]) << ' ' << ans << ' ';
ct2[t]--;
ct21[t] -= get1s(v);
if (c[0] == 1) ct21[t]++;
ct2[0]--;
ct21[0] -= get1s(v);
lol[2].upd(backord[v], -1);
int T = ct0[0] - ct0[t];
if (c[0] == 0) T--;
tans -= T;
}
c[v] = col;
if (c[v] == 0) {
int TT = get1s(v);
if (c[0] == 1) TT--;
ans += TT * (ct2[0] - ct2[t]);
ans += get21(t);
ct0[t]++;
ct01[t] += get1s(v);
if (c[0] == 1) ct01[t]--;
ct0[0]++;
ct01[0] += get1s(v);
lol[0].upd(backord[v], 1);
int T = ct2[0] - ct2[t];
if (c[0] == 2) T--;
tans += T;
}
if (c[v] == 1) {
ans += get0s(v) * (ct2[0] - ct2[t]);
ans += get2s(v) * (ct0[0] - ct0[t]);
ct01[0] += get0s(v);
ct21[0] += get2s(v);
upd(v, 1);
}
if (c[v] == 2) {
int TT = get1s(v);
if (c[0] == 1) TT--;
ans += TT * (ct0[0] - ct0[t]);
ans += get01(t);
ct2[t]++;
ct21[t] += get1s(v);
if (c[0] == 1) ct21[t]--;
ct2[0]++;
ct21[0] += get1s(v);
lol[2].upd(backord[v], 1);
int T = ct0[0] - ct0[t];
if (c[0] == 0) T--;
tans += T;
}
e = t;
}
long long getans() {
if (c[0] == 1) return ans + tans;
return ans;
}
};
vector<HLD> lol;
vector<int> sz, cc, ord;
vector<vector<int>> p;
void dfssz(int v, int pr) {
sz[v] = 1;
for (auto e : g[v]) {
if (e == pr) continue;
if (cc[e] != -1) continue;
dfssz(e, v);
sz[v] += sz[e];
}
ord.push_back(v);
}
void find_centroid(int v, int d) {
ord.clear();
dfssz(v, -1);
int N = sz[v];
int cntr = -1;
for (auto &e : ord) {
if (sz[e] > N / 2) {
cntr = e;
swap(e, ord[0]);
break;
}
}
lol[cntr].build(ord);
cc[cntr] = d;
for (auto e : ord) {
p[d][e] = cntr;
}
for (auto e : g[cntr]) {
if (cc[e] == -1) {
find_centroid(e, d + 1);
}
}
}
void init(int N, std::vector<int> F, std::vector<int> U, std::vector<int> V, int Q) {
g.resize(N);
sz.resize(N);
p.resize(20, vector<int>(N));
cc.resize(N, -1);
col = F;
for (int i = 0; i < N - 1; ++i) {
g[U[i]].push_back(V[i]);
g[V[i]].push_back(U[i]);
}
lol.resize(N);
find_centroid(0, 0);
for (auto e : lol) anss += e.getans();
}
void change(int X, int Y) {
for (int i = 0; i <= cc[X]; ++i) {
anss -= lol[p[i][X]].getans();
lol[p[i][X]].kek1(X, Y);
anss += lol[p[i][X]].getans();
}
}
long long num_tours() {
return anss;
}
#ifdef LOCAL
int main() {
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
int N;
assert(scanf("%d", &N) == 1);
std::vector<int> F(N);
for (int i = 0; i < N; i++) {
assert(scanf("%d", &F[i]) == 1);
}
std::vector<int> U(N - 1), V(N - 1);
for (int j = 0; j < N - 1; j++) {
assert(scanf("%d %d", &U[j], &V[j]) == 2);
}
int Q;
assert(scanf("%d", &Q) == 1);
init(N, F, U, V, Q);
printf("%lld\n", num_tours());
fflush(stdout);
for (int k = 0; k < Q; k++) {
int X, Y;
assert(scanf("%d %d", &X, &Y) == 2);
change(X, Y);
printf("%lld\n", num_tours());
fflush(stdout);
}
}
#endif
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 4712kb
input:
400 1 1 0 2 2 0 2 1 1 1 1 0 1 2 2 2 2 0 0 2 0 2 0 2 1 1 2 2 1 2 1 0 1 2 2 2 0 0 0 2 1 2 2 0 0 0 1 2 1 1 0 1 1 2 1 2 2 2 1 1 0 1 1 1 2 2 1 1 0 0 1 1 0 0 1 1 1 2 2 2 1 1 2 1 1 1 0 2 0 2 1 0 1 1 2 0 0 2 1 0 2 2 1 0 0 0 0 1 1 1 0 1 2 1 1 1 2 0 2 2 0 2 0 1 0 1 1 1 1 0 1 1 0 0 0 2 2 0 2 2 2 1 1 0 1 2 0 1 ...
output:
597892 604438 604222 600458 598015 594436 593625 586019 582403 581750 586857 587940 591404 592133 589209 587741 591739 595777 591792 591577 593683 592092 587464 583167 582283 580846 576415 577726 579563 578399 577998 577041 577680 584022 591611 594461 591140 590147 583481 582592 581026 585738 587414...
result:
wrong answer
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Time Limit Exceeded
Test #11:
score: 0
Time Limit Exceeded
input:
200000 0 2 2 0 2 2 0 1 1 0 2 2 0 1 2 2 0 1 0 2 1 1 0 1 0 2 0 2 0 0 0 1 0 0 2 0 2 1 0 0 1 1 1 0 0 2 1 2 2 1 0 2 2 2 0 2 2 1 2 0 1 0 0 1 2 0 0 2 1 1 1 0 1 1 1 2 1 0 1 1 0 1 2 2 2 0 1 0 1 1 0 2 0 1 0 2 0 0 2 2 2 2 2 0 0 2 1 2 2 1 2 0 1 1 1 1 1 0 2 0 2 0 1 1 1 0 1 0 2 1 2 0 1 1 0 2 1 2 2 2 0 0 2 2 2 0 1...
output:
77241161705660
result:
Subtask #4:
score: 0
Wrong Answer
Test #38:
score: 16
Accepted
time: 1ms
memory: 3788kb
input:
3 1 1 1 0 1 1 2 100 2 0 0 0 0 2 2 1 0 1 0 0 0 1 0 0 1 0 2 2 0 1 0 0 0 1 1 1 0 0 2 0 2 1 2 2 0 2 2 1 2 2 2 0 0 1 2 1 0 2 0 1 2 0 2 1 0 0 2 0 2 1 2 2 0 2 2 0 0 0 2 1 2 0 2 2 1 2 0 1 1 1 2 1 0 0 0 2 0 1 0 0 1 2 1 0 1 2 1 0 0 1 2 2 2 1 2 2 0 2 1 2 2 1 0 0 0 2 0 1 1 1 2 0 0 0 1 2 0 2 0 0 1 0 0 1 0 2 2 1 ...
output:
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0
result:
ok
Test #39:
score: 0
Wrong Answer
time: 1ms
memory: 3788kb
input:
4 2 2 2 0 0 1 1 2 2 3 100 0 0 3 2 1 1 3 1 0 2 2 0 1 0 3 0 0 1 1 2 0 0 3 2 3 1 1 0 3 2 3 0 3 1 1 2 3 2 0 1 2 2 2 1 1 0 1 1 1 0 3 0 0 2 1 2 0 0 3 1 1 0 2 0 3 0 2 2 3 2 0 2 0 1 3 1 2 1 3 0 1 2 2 2 3 2 2 1 1 1 3 1 1 2 2 0 0 2 1 1 0 1 3 0 2 2 0 2 0 0 1 0 3 1 2 1 0 2 2 2 0 0 0 1 3 0 2 1 1 2 3 1 3 2 1 1 2 ...
output:
0 0 0 1 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 -1 1 1 2 3 2 0 0 1 2 1 0 0 0 0 0 1 2 0 -2 -1 -2 -1 0 2 2 2 1 3 0 1 1 1 -1 0 0 -1 -1 -1 1 2 3 0 0 -1 0 -1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 2 2 2 1 1 1 0 0 0 1 1 2 1
result:
wrong answer
Subtask #5:
score: 0
Wrong Answer
Test #60:
score: 16
Accepted
time: 1ms
memory: 3900kb
input:
3 2 0 0 0 1 0 2 100 0 1 2 2 2 1 1 1 0 0 2 2 1 2 0 2 0 1 0 0 0 1 0 2 2 1 1 0 2 2 2 0 0 0 0 2 1 1 1 2 2 2 2 1 0 0 2 2 0 1 1 0 0 0 2 0 1 1 1 0 2 1 2 0 0 2 0 1 2 2 1 1 0 0 0 1 2 1 0 0 2 0 0 1 2 1 2 0 0 2 2 2 0 1 2 0 0 0 0 1 2 1 0 2 0 1 0 2 2 2 1 0 1 1 1 2 1 0 1 2 1 0 0 0 1 1 0 1 1 0 2 0 1 2 1 0 0 2 0 0 ...
output:
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok
Test #61:
score: 0
Wrong Answer
time: 1ms
memory: 3820kb
input:
4 1 0 1 0 0 1 0 2 1 3 100 0 2 3 2 1 1 0 1 3 1 3 2 3 1 2 2 1 2 2 1 1 0 2 2 3 2 3 1 1 1 3 2 2 0 3 1 0 2 1 2 2 1 2 2 0 1 1 0 3 0 3 2 3 1 3 0 0 0 2 0 1 1 1 2 0 1 1 0 2 2 2 1 1 1 3 2 0 0 2 2 0 1 3 1 1 0 2 1 2 0 1 2 0 2 3 0 3 1 0 1 0 2 3 2 3 1 1 1 1 0 2 2 0 0 0 1 0 0 0 1 0 0 2 0 0 1 3 2 0 2 3 0 2 2 2 1 3 ...
output:
0 0 0 0 0 0 0 0 0 0 0 1 2 2 2 0 0 2 0 0 0 0 0 0 2 4 2 2 4 2 2 1 1 2 2 4 2 1 1 2 2 1 0 2 1 1 2 1 2 1 2 1 2 1 0 1 1 1 2 1 2 1 1 1 3 2 2 2 2 2 2 2 2 2 4 3 2 2 2 2 2 2 2 2 2 2 2 2 1 0 1 1 2 2 2 2 2 1 1 1 1
result:
wrong answer
Subtask #6:
score: 0
Skipped
Dependency #2:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
0%