QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#411613	#7767. 数据结构	Terac	0	1353ms	307820kb	C++14	6.4kb	2024-05-15 16:38:14	2024-05-15 16:38:14

Judging History

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

[2024-05-15 16:38:14]
评测

测评结果：0
用时：1353ms
内存：307820kb

查看

[2024-05-15 16:38:14]
提交

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 = 1; 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
*/

源文件, 语言: C++14

詳細信息

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 0

Wrong Answer

time: 25ms

memory: 106620kb

input:

output:

22530221648
1551434412746
2043593513572
916136908202
1149041304048
1930351776826
5627975877317
1741813781164
5497206096345
2186592622
3750422895688
1674542130
6524658548
6568501816645
8480988593454
10287912614914
492570862
2712528038832
2834694279
948024175
4395772262
4221137767
9630829210
863214422...

result:

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

Subtask #2:

score: 0

Wrong Answer

Test #3:

score: 0

Wrong Answer

time: 943ms

memory: 296092kb

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
3288575788
3288575788
0
3834750343
3834750343
0
0
4489794361
0
0
5224818790
5224818790
5224818790
5961407442
0
6668272644
0
0
8307321880
0
0
0
0
8340628337
0
0
8340628337
0
8850837817
0
0
9699348101
9699348101
9699348101
0
9699348101
0
9828272482
0
9828272482
9828272482
0
0
101871097...

result:

wrong answer 9th numbers differ - expected: '7615073807', found: '3288575788'

Subtask #3:

score: 0

Wrong Answer

Test #5:

score: 0

Wrong Answer

time: 471ms

memory: 307820kb

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
172304962
179523849291973
75824457254155
143778236366329
219466451073683
224340027176315
163353112374085
262654242884320
206555771768027
3803430930
1896237350
448431934080
359102756720054
693712416606751
740996329746934
215244492677161
18206270459578
4...

result:

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

Subtask #4:

score: 0

Wrong Answer

Test #7:

score: 0

Wrong Answer

time: 1353ms

memory: 300204kb

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:

result:

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

Subtask #5:

score: 0

Skipped

Dependency #4:

Subtask #6:

score: 0

Skipped

Dependency #4:

Subtask #7:

score: 0

Skipped

Dependency #2:

Subtask #8:

score: 0

Skipped

QOJ.ac

QOJ

Judging History

answer

詳細信息

Subtask #1:

Test #1:

input:

output:

result:

Subtask #2:

Test #3:

input:

output:

result:

Subtask #3:

Test #5:

input:

output:

result:

Subtask #4:

Test #7:

input:

output:

result:

Subtask #5:

Dependency #4:

Subtask #6:

Dependency #4:

Subtask #7:

Dependency #2:

Subtask #8:

Dependency #1: