QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#411617#7767. 数据结构Terac10 1521ms354476kbC++146.4kb2024-05-15 16:40:172024-05-15 16:40:17

Judging History

你现在查看的是最新测评结果

  • [2024-05-15 16:40:17]
  • 评测
  • 测评结果:10
  • 用时:1521ms
  • 内存:354476kb
  • [2024-05-15 16:40:17]
  • 提交

answer

#include <bits/stdc++.h>
#define pii pair<int, int>
#define fir first
#define sec second
#define ull unsigned long long
using namespace std;

namespace IO {
	#if ONLINE_JUDGE
	#define getc() (IS == IT && (IT = (IS = ibuf) + fread(ibuf, 1, IL, stdin), IS == IT) ? EOF : *IS++)
	#else
	#define getc() getchar()
	#endif
	const int IL = 1 << 21, OL = 1 << 21;
	int olen = 0;
	char ibuf[IL], *IS = ibuf, *IT = ibuf, obuf[OL];
	inline int read() {
		register char ch = getc(); register int x = 0, f = 1;
		while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getc(); }
		while(isdigit(ch)) x = x * 10 + ch - 48, ch = getc();
		return x * f;
	}
	inline double readdb() {
		register char ch = getc(); register double x = 0, f = 1;
		while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getc(); }
		while(isdigit(ch)) x = x * 10 + ch - 48, ch = getc();
		if(ch == '.') {
			register double b = 0.1;
			ch = getc();
			while(isdigit(ch)) x += (ch - 48) * b, b *= 0.1, ch = getc();
		}
		return x * f;
	}
	inline int readstr(char *s) {
		register char ch = getc(); register int len = 0;
		while(!isalpha(ch)) ch = getc();
		while(isalpha(ch)) s[++len] = ch, ch = getc();
		return len;
	}
	inline void flush() { fwrite(obuf, 1, olen, stdout); olen = 0; }
	inline void putc(register char ch) { obuf[olen++] = ch; }
	template<class T>
	inline void write(register T x) {
		if(x < 0) obuf[olen++] = '-', x = -x;
		if(x > 9) write(x / 10);
		obuf[olen++] = x % 10 + 48;
	}
} using namespace IO;
const int N = 2e5 + 10;
int n, k, q, tim;
int fa[N], dep[N], siz[N], dfn[N], id[N], top[N];
namespace bit {
	ull t1[N], t2[N];
	void add1(int x, ull k) {
		for(int i = x; i <= n; i += i & -i)
			t1[i] += k;
	}
	void add2(int x, ull k) {
		for(int i = x; i <= n; i += i & -i)
			t2[i] += k;
	}
	ull qry1(int x) {
		ull res = 0;
		for(int i = x; i; i -= i & -i)
			res += t1[i];
		return res;
	}
	ull qry2(int x) {
		ull res = 0;
		for(int i = x; i; i -= i & -i)
			res += t2[i];
		return res;
	}
	ull qry(int l, int r) {
		return qry2(r) * r + qry1(r) - qry2(l - 1) * (l - 1) - qry1(l - 1);
	}
	void add(int l, int r, ull k) {
//		cout << "add:" << l << " " << r << " " << k << endl;
		add1(l, -k * (l - 1)), add1(r + 1, k * r);
		add2(l, k), add2(r + 1, -k);
//		cout << qry(1, 7) << endl;
	}
} using namespace bit;
vector<int> E[N], e[N];
vector<pii> son[N][4], ans[N][4], fk[N][4], lf[N][4], st[N];
bool cmp(int x, int y) { return siz[x] > siz[y]; }
void dfs1(int u, int f) {
	fa[u] = f, dep[u] = dep[f] + 1, siz[u] = 1;
	for(auto v : E[u]) {
		if(v == f) continue;
		e[u].push_back(v);
		dfs1(v, u);
		siz[u] += siz[v];
	}
	sort(e[u].begin(), e[u].end(), cmp);
}
void merge(vector<pii> &x) {
	vector<pii> vc;
	sort(x.begin(), x.end());
	for(auto r : x) {
		if(vc.size() && r.fir == vc.back().sec + 1) vc[vc.size() - 1].sec = r.second;
		else vc.push_back(r);
	}
	x = vc;
}
void merge(vector<pii> &x, vector<pii> y) {
	for(auto r : y) x.push_back(r);
	merge(x);
}
void nt(int u, int d) {
	if(!d) {
		if(!dfn[u]) dfn[u] = ++tim, id[tim] = u;
		return;
	}
	for(auto v : e[u]) nt(v, d - 1);
}
void dfs2(int u) {
	vector<int> vc;
	int v = u;
	while(1) {
		top[v] = u;
		if(!dfn[v]) dfn[v] = ++tim, id[tim] = v;
		vc.push_back(v);
		if(!e[v].size()) break;
		v = e[v][0];
	}
	for(int i = 1; i <= k; i++)
		for(auto x : vc)
			nt(x, i);
	for(int i = vc.size() - 1; ~i; i--)
		for(int j = 1; j < e[vc[i]].size(); j++)
			dfs2(e[vc[i]][j]);
}
void dfs3(int u) {
	son[u][0].push_back({dfn[u], dfn[u]});
	st[u].push_back({dfn[u], dfn[u]});
	for(auto v : e[u]) {
		dfs3(v);
		merge(st[u], st[v]);
		for(int i = 0; i <= k; i++)
			merge(fk[v][i], son[u][i]);
		for(int i = 1; i <= k; i++)
			merge(son[u][i], son[v][i - 1]);
	}
	vector<pii> tmp[11];
	for(int i = e[u].size() - 1, v; ~i; i--) {
		v = e[u][i];
		for(int i = 1; i <= k; i++)
			merge(fk[v][i], tmp[i]);
		for(int i = 1; i <= k; i++)
			merge(tmp[i], son[v][i - 1]);
	}
}
void dfs4(int u) {
	ans[u][0].push_back({dfn[u], dfn[u]});
	for(int i = 0; i <= k; i++)
		lf[u][i] = lf[fa[u]][i];
	if(u == 1) {
		lf[u][0] = son[u][0];
		for(int i = 1; i <= k; i++)
			lf[u][i] = lf[u][i - 1], merge(lf[u][i], son[u][i]);
	}
	else
		for(int i = 0; i <= k; i++)
			merge(lf[u][i], son[u][i]);
	for(int i = 1; i <= k; i++) {
		ans[u][i] = son[u][i];
		for(int j = 1, f = u; fa[f] && j <= i; f = fa[f], j++)
			merge(ans[u][i], fk[f][i - j]);
	}
	for(auto v : e[u]) dfs4(v);
}
int LCA(int u, int v) {
	while(top[u] != top[v]) {
		if(dep[top[u]] < dep[top[v]]) swap(u, v);
		u = fa[top[u]];
	}
	return dep[u] < dep[v] ? u : v;
}
int main() {
	n = read(), q = read();
	k = 3;
	for(int i = 1; i < n; i++) {
		int u = read(), v = read();
		E[u].push_back(v);
		E[v].push_back(u);
	}
	dfs1(1, 0);
	dfs2(1);
	dfs3(1);
	dfs4(1);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= k; j++)
			merge(ans[i][j], ans[i][j - 1]);
//	for(int i =1; i <= n;i++)
//		cout<< "dfn:" << i << " " << dfn[i] << endl;
//	for(int i = 1; i <= n; i++) {
//		cout << i << "\n\n";
//		for(int j = 0; j <= 0; puts(""), j++)
//			for(auto x : lf[i])
//				cout << "["<<x.fir << " " << x.sec << "]"<< endl; 
//	} 
//			printf("%d\n", query(1, 1, n, dfn[1]));
//	for(int i =1; i <= n; puts(""), i++)
//		for(auto x : lf[i][3])
//			cout << "pos:"<<i<<" " << "["<<x.fir << " "<<x.sec <<"]"<< endl;
	while(q--) {
		int op = read();
		if(op == 1) {
			int u = read(), v = read(), k = read(), t = read();
			int f = LCA(u, v);
			for(auto x : lf[u][k])
				add(x.fir, x.sec, t);
			for(auto x : lf[v][k])
				add(x.fir, x.sec, t);
			for(auto x : lf[f][k])
				add(x.fir, x.sec, -t);
			for(auto x : lf[fa[f]][k])
				add(x.fir, x.sec, -t);
		}
		if(op == 2) {
			int u = read(), v = read();
//			cout << "!!!:" << st[u].size() << endl;
			for(auto x : st[u])
				add(x.fir, x.sec, v);
		}
		if(op == 3) {
			int u = read(), v = read(), k = read();
			int f = LCA(u, v);
			ull ans = 0;
			for(auto x : lf[u][k])
				ans += qry(x.fir, x.sec);
			for(auto x : lf[v][k])
				ans += qry(x.fir, x.sec);
			for(auto x : lf[f][k])
				ans -= qry(x.fir, x.sec);
			for(auto x : lf[fa[f]][k])
				ans -= qry(x.fir, x.sec);
			printf("%llu\n", ans);
		}
		if(op == 4) {
			int u = read();
			ull ans = 0;
			for(auto x : st[u])
				ans += qry(x.fir, x.sec);
			printf("%llu\n", ans);
		}
	}
	return 0;
}
/*
7 6
1 2
2 3
1 4
4 5
1 6
6 7
1 1 5 3 4
2 3 5
3 1 5 3
4 5
4 3
4 2
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 20ms
memory: 97772kb

input:

5000 5000
1 2
2 3
3 4
4 5
5 6
5 7
6 8
7 9
9 10
8 11
11 12
12 13
12 14
14 15
15 16
16 17
16 18
18 19
18 20
20 21
20 22
22 23
23 24
23 25
23 26
26 27
27 28
28 29
27 30
30 31
29 32
32 33
33 34
32 35
35 36
36 37
35 38
36 39
38 40
38 41
41 42
42 43
43 44
42 45
44 46
45 47
47 48
48 49
48 50
49 51
51 52
52...

output:

32933561120
2130120170876
2794367845468
1305828665924
1690448429070
2678958746332
6681417865297
2079488841526
5786332239171
2186592622
4014965079076
1674542130
6524658548
7091052607583
10040980978798
11583010045454
492570862
3333441131196
2834694279
4188546805364
4395772262
4221137767
9630829210
989...

result:

wrong answer 1st numbers differ - expected: '37227703492', found: '32933561120'

Subtask #2:

score: 10
Accepted

Test #3:

score: 10
Accepted
time: 1226ms
memory: 318720kb

input:

200000 200000
1 2
1 3
1 4
3 5
1 6
1 7
7 8
8 9
2 10
1 11
5 12
1 13
7 14
10 15
2 16
7 17
11 18
5 19
5 20
1 21
16 22
1 23
3 24
20 25
14 26
2 27
6 28
15 29
10 30
15 31
5 32
13 33
12 34
31 35
31 36
36 37
36 38
1 39
28 40
5 41
12 42
41 43
20 44
30 45
22 46
11 47
47 48
45 49
14 50
41 51
3 52
30 53
29 54
6 ...

output:

0
0
0
0
0
0
0
0
7615073807
4176911055
0
4745654848
6222845818
0
0
9739142819
0
1424960716
5224818790
9459319003
13717923473
8673060864
0
11610197664
0
0
9587792729
0
0
0
2747489046
12425650803
0
0
11191496476
0
37597503993
0
0
15164651949
14868775382
15559673116
0
16391028892
0
15726757336
0
2421390...

result:

ok 100169 numbers

Test #4:

score: 10
Accepted
time: 1302ms
memory: 354476kb

input:

200000 200000
121679 2
13340 3
45206 4
112138 5
47397 6
88216 7
173469 8
109861 9
58662 10
130056 11
61155 12
4313 13
196310 14
46189 15
32349 16
143798 17
103215 18
159921 19
27365 20
14332 21
49504 22
64451 23
106931 24
59878 25
177587 26
100555 27
86848 28
793 29
79845 30
150813 31
42854 32
11551...

output:

77900221111
0
0
476439705914
0
216029652830
0
0
631267909751
508097390689
0
29277716182
695169620128
0
809294022024
0
0
829507748883
260130797154
0
1005527232590
109198360548
821333235719
0
0
1265757368752
738460021055
296232170804
845184728833
0
434366813420
0
1922343637889
0
0
0
229703081048
0
441...

result:

ok 100073 numbers

Subtask #3:

score: 0
Wrong Answer

Test #5:

score: 0
Wrong Answer
time: 506ms
memory: 305740kb

input:

200000 200000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 ...

output:

0
134313322523733
38210069287857
75885012627846
25202076347900
179523849291973
75824457254155
156951554536901
246507909884129
251381485986761
181645863942433
285463128028270
213787601973331
244899810363137
53370719292672
448431934080
379306317440032
720753875417197
768639337974684
224741669585515
18...

result:

wrong answer 2nd numbers differ - expected: '134315201201061', found: '134313322523733'

Subtask #4:

score: 0
Wrong Answer

Test #7:

score: 0
Wrong Answer
time: 1521ms
memory: 324196kb

input:

200000 200000
1 2
2 3
3 4
1 5
3 6
5 7
5 8
7 9
2 10
7 11
11 12
10 13
6 14
3 15
14 16
4 17
11 18
3 19
14 20
4 21
4 22
12 23
18 24
5 25
5 26
14 27
13 28
24 29
11 30
26 31
29 32
28 33
31 34
23 35
33 36
6 37
11 38
22 39
13 40
35 41
37 42
21 43
12 44
4 45
16 46
12 47
21 48
1 49
26 50
45 51
41 52
46 53
7 5...

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:

wrong answer 259th numbers differ - expected: '782172417', found: '0'

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #4:

0%

Subtask #7:

score: 0
Skipped

Dependency #2:

100%
Accepted

Dependency #4:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

0%