QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#945034 | #7443. vti | zlt | WA | 280ms | 139088kb | C++14 | 6.7kb | 2025-03-20 18:45:07 | 2025-03-20 18:45:15 |
Judging History
answer
// Problem: P8205 [Ynoi2005] vti
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8205
// Memory Limit: 512 MB
// Time Limit: 1500 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
namespace IO {
const int maxn = 1 << 20;
char ibuf[maxn], *iS, *iT, obuf[maxn], *oS = obuf;
inline char gc() {
return (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++) : *iS++);
}
template<typename T = int>
inline T read() {
char c = gc();
T x = 0;
bool f = 0;
while (c < '0' || c > '9') {
f |= (c == '-');
c = gc();
}
while (c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (c ^ 48);
c = gc();
}
return f ? ~(x - 1) : x;
}
inline void flush() {
fwrite(obuf, 1, oS - obuf, stdout);
oS = obuf;
}
struct Flusher {
~Flusher() {
flush();
}
} AutoFlush;
inline void pc(char ch) {
if (oS == obuf + maxn) {
flush();
}
*oS++ = ch;
}
template<typename T>
inline void write(T x) {
static char stk[64], *tp = stk;
if (x < 0) {
x = ~(x - 1);
pc('-');
}
do {
*tp++ = x % 10;
x /= 10;
} while (x);
while (tp != stk) {
pc((*--tp) | 48);
}
}
template<typename T>
inline void writesp(T x) {
write(x);
pc(' ');
}
template<typename T>
inline void writeln(T x) {
write(x);
pc('\n');
}
}
using IO::read;
using IO::write;
using IO::pc;
using IO::writesp;
using IO::writeln;
const int maxn = 2000100;
const int logn = 20;
int n, m, a[maxn], dfn[maxn], tim, st[logn][maxn / 20];
ll ans[maxn];
inline int get(int i, int j) {
return dfn[i] < dfn[j] ? i : j;
}
inline int qlca(int x, int y) {
if (x == y) {
return x;
}
x = dfn[x];
y = dfn[y];
if (x > y) {
swap(x, y);
}
++x;
int k = __lg(y - x + 1);
return get(st[k][x], st[k][y - (1 << k) + 1]);
}
struct graph {
int hd[maxn], len, to[maxn], nxt[maxn];
inline void add_edge(int u, int v) {
to[++len] = v;
nxt[len] = hd[u];
hd[u] = len;
}
} G;
int tot, in[maxn];
pii ord[maxn];
void dfs(int u, int t) {
dfn[u] = ++tim;
st[0][tim] = t;
if (u > 1) {
ord[++tot] = mkp(a[u], 1);
in[u] = tot;
}
for (int i = G.hd[u]; i; i = G.nxt[i]) {
int v = G.to[i];
if (v == t) {
continue;
}
dfs(v, u);
}
if (u > 1) {
ord[++tot] = mkp(a[u], -1);
}
}
int b[maxn], K, c[maxn], tq, bel[maxn], blo;
struct que {
int l, r, o, i;
ll ans;
que(int a = 0, int b = 0, int c = 0, int d = 0, ll e = 0) : l(a), r(b), o(c), i(d), ans(e) {}
} qq[maxn];
namespace BIT {
int c[maxn];
inline void update(int x, int d) {
for (int i = x; i <= n; i += (i & (-i))) {
c[i] += d;
}
}
inline int query(int x) {
int res = 0;
for (int i = x; i; i -= (i & (-i))) {
res += c[i];
}
return res;
}
}
ll f[maxn], g[maxn];
struct line {
int l, r, o, i;
line(int a = 0, int b = 0, int c = 0, int d = 0) : l(a), r(b), o(c), i(d) {}
};
struct List {
int hd[maxn], len, nxt[maxn];
line to[maxn];
inline void add(int x, line y) {
to[++len] = y;
nxt[len] = hd[x];
hd[x] = len;
}
} L1, L2;
namespace DS {
int bel[maxn], blo, L[maxn], R[maxn], a[maxn], b[maxn];
inline void init() {
blo = sqrt(n);
for (int i = 1; i <= n; ++i) {
bel[i] = (i - 1) / blo + 1;
if (!L[bel[i]]) {
L[bel[i]] = i;
}
R[bel[i]] = i;
}
}
inline void update(int x, int y) {
for (int i = x; i <= R[bel[x]]; ++i) {
a[i] += y;
}
for (int i = bel[x] + 1; i <= bel[n]; ++i) {
b[i] += y;
}
}
inline int query(int x) {
return a[x] + b[bel[x]];
}
}
void solve() {
n = read();
for (int i = 2; i <= n; ++i) {
int p = read();
a[i] = read();
G.add_edge(p, i);
}
dfs(1, 0);
for (int j = 1; (1 << j) <= n; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
st[j][i] = get(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
}
m = read();
for (int i = 1; i <= m; ++i) {
K = read();
for (int j = 1; j <= K; ++j) {
b[j] = read();
}
if (K == 1) {
continue;
}
sort(b + 1, b + K + 1, [&](const int &x, const int &y) {
return dfn[x] < dfn[y];
});
int t = K;
for (int j = 1; j < t; ++j) {
b[++K] = qlca(b[j], b[j + 1]);
}
sort(b + 1, b + K + 1, [&](const int &x, const int &y) {
return dfn[x] < dfn[y];
});
K = unique(b + 1, b + K + 1) - b - 1;
for (int j = 1; j <= K; ++j) {
c[b[j]] = 0;
}
for (int j = 1; j < K; ++j) {
int u = qlca(b[j], b[j + 1]);
++c[u];
}
for (int j = 2; j <= K; ++j) {
qq[++tq] = que(in[b[1]] + 1, in[b[j]], 1 - c[b[j]], i);
}
}
blo = ceil(tot / sqrt(tq));
for (int i = 1; i <= tot; ++i) {
bel[i] = (i - 1) / blo + 1;
}
sort(qq + 1, qq + tq + 1, [&](const que &a, const que &b) {
if (bel[a.l] != bel[b.l]) {
return bel[a.l] < bel[b.l];
} else if (bel[a.l] & 1) {
return a.r < b.r;
} else {
return a.r > b.r;
}
});
for (int i = 1; i <= tot; ++i) {
f[i] = f[i - 1] + BIT::query(ord[i].fst - 1) * ord[i].scd;
g[i] = g[i - 1] + (i - 1 - BIT::query(ord[i].fst)) * ord[i].scd;
BIT::update(ord[i].fst, ord[i].scd);
}
int l = 1, r = 0;
for (int i = 1; i <= tq; ++i) {
int ql = qq[i].l, qr = qq[i].r;
if (l > ql) {
qq[i].ans -= g[l - 1] - g[ql - 1];
L2.add(r, line(ql, l - 1, 1, i));
l = ql;
}
if (r < qr) {
qq[i].ans += f[qr] - f[r];
L1.add(l - 1, line(r + 1, qr, -1, i));
r = qr;
}
if (l < ql) {
qq[i].ans += g[ql - 1] - g[l - 1];
L2.add(r, line(l, ql - 1, -1, i));
l = ql;
}
if (r > qr) {
qq[i].ans -= f[r] - f[qr];
L1.add(l - 1, line(qr + 1, r, 1, i));
r = qr;
}
}
DS::init();
for (int i = 1; i <= tot; ++i) {
DS::update(ord[i].fst, ord[i].scd);
for (int _ = L1.hd[i]; _; _ = L1.nxt[_]) {
line u = L1.to[_];
for (int j = u.l; j <= u.r; ++j) {
qq[u.i].ans += u.o * ord[j].scd * DS::query(ord[j].fst - 1);
}
}
for (int _ = L2.hd[i]; _; _ = L2.nxt[_]) {
line u = L2.to[_];
for (int j = u.l; j <= u.r; ++j) {
qq[u.i].ans += u.o * ord[j].scd * (i - DS::query(ord[j].fst));
}
}
}
for (int i = 1; i <= tq; ++i) {
qq[i].ans += qq[i - 1].ans;
ans[qq[i].i] += qq[i].ans * qq[i].o;
}
for (int i = 1; i <= m; ++i) {
writeln(ans[i]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 63ms
memory: 131400kb
input:
100000 1 19270 2 16523 3 72807 3 48950 2 41661 2 74623 2 11727 6 13478 1 40534 1 20287 5 22016 7 56368 3 55726 7 38294 14 77270 16 34784 9 81185 8 47123 3 44430 17 27172 20 87246 13 65 10 17478 3 10313 25 28816 12 76911 25 52410 8 71803 1 57285 12 8264 3 92423 17 49511 9 5194 5 85403 6 43755 2 66620...
output:
23008 21632 15760 21770 23886 20526 18436 19302 24195 16780 16056 17013 20558 15483 25016 16175 20203 15728 17132 19926 21240 23774 16018 25231 24829 19085 16020 24923 17060 16607 18537 23509 14832 22176 25325 25419 15509 17850 23361 27148 19474 24186 21217 24400 22926 19315 19724 26624 19179 23353 ...
result:
ok 100 numbers
Test #2:
score: 0
Accepted
time: 121ms
memory: 137156kb
input:
100000 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 1 60 1 61...
output:
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 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 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 ...
result:
ok 666646 numbers
Test #3:
score: 0
Accepted
time: 280ms
memory: 131520kb
input:
100000 1 1 2 1 1 1 3 1 1 1 1 1 6 1 6 1 9 1 5 1 8 1 5 1 13 1 8 1 10 1 8 1 3 1 16 1 13 1 17 1 9 1 8 1 13 1 17 1 23 1 5 1 21 1 5 1 9 1 20 1 12 1 25 1 24 1 23 1 13 1 7 1 18 1 3 1 10 1 16 1 31 1 21 1 42 1 20 1 35 1 20 1 17 1 6 1 6 1 9 1 46 1 16 1 19 1 15 1 2 1 10 1 24 1 13 1 9 1 47 1 17 1 20 1 44 1 13 1 ...
output:
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 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 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 ...
result:
ok 9980 numbers
Test #4:
score: -100
Wrong Answer
time: 242ms
memory: 139088kb
input:
100000 1 3 2 13 2 9 1 2 5 15 3 4 7 8 2 2 4 9 7 2 4 5 2 9 8 12 2 9 7 16 1 4 1 3 15 14 6 18 17 15 11 4 21 11 14 1 3 4 25 11 20 19 8 9 7 7 27 7 3 17 18 19 32 2 22 7 3 4 6 1 36 14 8 5 22 3 16 11 23 15 8 19 37 10 37 14 32 3 32 7 20 6 1 12 41 18 44 13 29 11 12 17 19 10 41 13 6 8 9 10 54 19 54 15 58 2 54 1...
output:
-46804 105 35 95 100 10975 77 111 144 151 74 51 58 143 112 113 161 89 88 110 244 67 97 251209 68 -669833 97 251162 29 152 158 -669842 -46764 103 101 121 154 87 102 117 124 -809528 141 101 105 93 63 170 40 43 149 102 117 -178597 109 94 45 199 122 45 251165 40 -361803 155 145 154 89 60 39 37 71 376671...
result:
wrong answer 1st numbers differ - expected: '52', found: '-46804'