QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#945034#7443. vtizltWA 280ms139088kbC++146.7kb2025-03-20 18:45:072025-03-20 18:45:15

Judging History

This is the latest submission verdict.

  • [2025-03-20 18:45:15]
  • Judged
  • Verdict: WA
  • Time: 280ms
  • Memory: 139088kb
  • [2025-03-20 18:45:07]
  • Submitted

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'