QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#767832#7767. 数据结构zhouhuanyi5 955ms382776kbC++177.2kb2024-11-20 22:17:462024-11-20 22:17:46

Judging History

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

  • [2024-11-20 22:17:46]
  • 评测
  • 测评结果:5
  • 用时:955ms
  • 内存:382776kb
  • [2024-11-20 22:17:46]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cassert>
#define N 200000
using namespace std;
int read()
{
	char c=0;
	int sum=0,f=1;
	while (c!='-'&&(c<'0'||c>'9')) c=getchar();
	if (c=='-') c=getchar(),f=-1;
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum*f;
}
struct reads
{
	int l,r;
};
reads operator + (reads a,reads b)
{
	return (reads){min(a.l,b.l),max(a.r,b.r)};
}
struct lines
{
	int x,y,data;
	bool operator < (const lines &t)const
	{
		return data<t.data;	
	}
};
lines dque[N+1];
int n,m,tops,dfn[N+1],leng,depth[N+1],rev[N+1],rev2[N+1],sz[N+1],top[N+1],fa[N+1],hs[N+1],num[N+1],length;
__int128 ans;
bool used[N+1];
vector<int>E[N+1];
vector<int>ES[N+1];
vector<int>p[N+1][4];
vector<reads>dp[N+1][4];
vector<reads>DP[N+1][4];
vector<reads>DP2[N+1];
bool cmp(int x,int y)
{
	return num[x]<num[y];
}
vector<reads>operator + (vector<reads>a,vector<reads>b)
{
	if (a.empty()) return b;
	if (b.empty()) return a;
	int ps=0,ps2=0;
	reads d=(reads){0,-1};
	vector<reads>sp;
	while (ps<a.size()||ps2<b.size())
	{
		if (ps<a.size()&&(ps2==b.size()||a[ps].l<b[ps2].l))
		{
			if (d.r+1>=a[ps].l) d=d+a[ps];
			else
			{
				if (d.l<=d.r) sp.push_back(d);
				d=a[ps];
			}
			ps++;
		}
		else
		{
			if (d.r+1>=b[ps2].l) d=d+b[ps2];
			else
			{
				if (d.l<=d.r) sp.push_back(d);
				d=b[ps2];
			}
			ps2++;
		}
	}
	sp.push_back(d);
	return sp;
}
vector<reads>operator * (vector<reads>a,vector<reads>b)
{
	if (a.empty()) return b;
	if (b.empty()) return a;
	int ps=0,ps2=0;
	reads d=(reads){0,-1};
	vector<reads>sp;
	while (ps<a.size()||ps2<b.size())
	{
		if (ps<a.size()&&(ps2==b.size()||a[ps].l<b[ps2].l))
		{
			if (d.r+1>=a[ps].l) d=d+a[ps];
			else
			{
				if (d.l<=d.r) sp.push_back(d);
				d=a[ps];
			}
			ps++;
		}
		else
		{
			if (d.r+1>=b[ps2].l) d=d+b[ps2];
			else
			{
				if (d.l<=d.r) sp.push_back(d);
				d=b[ps2];
			}
			ps2++;
		}
	}
	sp.push_back(d);
	if (sp.size()>=40) sp.clear(),sp.shrink_to_fit();
	return sp;
}
void add(int x,int y)
{
	E[x].push_back(y),E[y].push_back(x);
	return;
}
void dfs(int x)
{
	used[x]=sz[x]=1;
	for (int i=0;i<E[x].size();++i)
		if (!used[E[x][i]])
		{
			fa[E[x][i]]=x,depth[E[x][i]]=depth[x]+1,ES[x].push_back(E[x][i]),dfs(E[x][i]),sz[x]+=sz[E[x][i]];
			if (sz[E[x][i]]>sz[hs[x]]) hs[x]=E[x][i];
		}
	return;
}
void dfs2(int x)
{
	dfn[x]=++leng,rev[dfn[x]]=x;
	if (ES[x].empty()) dque[++tops]=(lines){top[x],x,depth[top[x]]};
	if (hs[x]) top[hs[x]]=top[x],dfs2(hs[x]);
	for (int i=0;i<ES[x].size();++i)
		if (ES[x][i]!=hs[x])
			top[ES[x][i]]=ES[x][i],dfs2(ES[x][i]);
	return;
}
void dfs3(int x)
{
	for (int i=0;i<ES[x].size();++i)
	{
		if (ES[x][i]==hs[x])
		{
			for (int j=0;j<=3;++j) DP[ES[x][i]][j]=DP[ES[x][i]][j]+DP[x][j];
		}
		dfs3(ES[x][i]),DP2[x]=DP2[x]+DP2[ES[x][i]],assert(DP2[x].size()<=8);
	}
	return;
}
struct seg
{
	struct node
	{
		int l,r;
		vector<reads>data;
	};
	node tree[(N<<2)+1];
	void push_up(int k)
	{
		tree[k].data=tree[k<<1].data*tree[k<<1|1].data;
		return;
	}
	void build(int k,int l,int r,int d)
	{
		tree[k].l=l,tree[k].r=r;
		if (l==r)
		{
			tree[k].data=dp[rev[l]][d];
			return;
		}
		int mid=(l+r)>>1;
		build(k<<1,l,mid,d),build(k<<1|1,mid+1,r,d),push_up(k);
		return;
	}
	vector<reads>query(int k,int l,int r)
	{
		if (tree[k].l==l&&tree[k].r==r) return tree[k].data;
		int mid=(tree[k].l+tree[k].r)>>1;
		if (r<=mid) return query(k<<1,l,r);
		else if (l>=mid+1) return query(k<<1|1,l,r);
		else return query(k<<1,l,mid)*query(k<<1|1,mid+1,r);
	}
};
seg T[4];
struct seg2
{
	struct node
	{
		int l,r;
		long long lazy;
		__int128 data;
	};
	node tree[(N<<2)+1];
	void push_up(int k)
	{
		tree[k].data=tree[k<<1].data+tree[k<<1|1].data;
		return;
	}
	void push_tag(int k,long long d)
	{
		tree[k].lazy+=d,tree[k].data+=(__int128)(d)*(tree[k].r-tree[k].l+1);
		return;
	}
	void spread(int k)
	{
		if (tree[k].lazy!=0) push_tag(k<<1,tree[k].lazy),push_tag(k<<1|1,tree[k].lazy),tree[k].lazy=0;
		return;
	}
	void build(int k,int l,int r)
	{
		tree[k].l=l,tree[k].r=r;
		if (l==r) return;
		int mid=(l+r)>>1;
		build(k<<1,l,mid),build(k<<1|1,mid+1,r),push_up(k);
		return;
	}
	void add(int k,int l,int r,int d)
	{
		if (tree[k].l==l&&tree[k].r==r)
		{
			push_tag(k,d);
			return;
		}
		spread(k);
		int mid=(tree[k].l+tree[k].r)>>1;
		if (r<=mid) add(k<<1,l,r,d);
		else if (l>=mid+1) add(k<<1|1,l,r,d);
		else add(k<<1,l,mid,d),add(k<<1|1,mid+1,r,d);
		push_up(k);
		return;
	}
	__int128 query(int k,int l,int r)
	{
		if (tree[k].l==l&&tree[k].r==r) return tree[k].data;
		spread(k);
		int mid=(tree[k].l+tree[k].r)>>1;
		if (r<=mid) return query(k<<1,l,r);
		else if (l>=mid+1) return query(k<<1|1,l,r);
		else return query(k<<1,l,mid)+query(k<<1|1,mid+1,r);
	}
};
seg2 T2;
vector<reads>get_path(int x,int y,int k)
{
	vector<reads>sp;
	while (top[x]!=top[y])
	{
		if (depth[top[x]]<depth[top[y]]) swap(x,y);
		sp=sp+DP[x][k],x=fa[top[x]];
	}
	if (depth[x]>depth[y]) swap(x,y);
	sp=sp+T[k].query(1,dfn[x],dfn[y]);
	return sp;
}
void write(__int128 d)
{
	if (!d) return;
	write(d/10),printf("%d",(int)(d%10));
	return;
}
void output(__int128 d)
{
	if (d>0) write(d),puts("");
	else if (d==0) puts("0");
	else printf("-"),write(-d),puts("");
	return;
}
int main()
{
	int opt,x,y,d,k;
	vector<reads>sp;
	n=read(),m=read();
	for (int i=1;i<=n-1;++i) x=read(),y=read(),add(x,y);
	depth[1]=1,dfs(1);
	for (int i=1;i<=n;++i)
	{
		x=i;
		for (int j=0;j<=3;++j)
		{
			if (x) p[x][j].push_back(i);
			x=fa[x];
		}
	}
	top[1]=1,dfs2(1),sort(dque+1,dque+tops+1);
	for (int i=1;i<=tops;++i)
	{
		x=dque[i].x;
		while (x)
		{
			if (!num[x]) num[x]=++length;
			x=hs[x];
		}
		for (int j=0;j<=2;++j)
		{
			x=dque[i].x;
			while (x)
			{
				for (int k=0;k<ES[x].size();++k)
					if (ES[x][k]!=hs[x])
					{
						for (int t=0;t<p[ES[x][k]][j].size();++t)
							if (!num[p[ES[x][k]][j][t]])
								num[p[ES[x][k]][j][t]]=++length;
					}
				x=hs[x];
			}
		}
	}
	for (int i=1;i<=n;++i) dp[i][0]={(reads){num[i],num[i]}},rev2[num[i]]=i;
	for (int i=1;i<=3;++i)
		for (int j=1;j<=n;++j)
		{
			dp[j][i]=dp[j][i-1];
			for (int t=0;t<E[j].size();++t) dp[j][i]=dp[j][i]+dp[E[j][t]][i-1],assert(dp[j][i].size()<=8);
		}
	for (int i=1;i<=n;++i)
	{
		for (int j=0;j<=3;++j) DP[i][j]=dp[i][j];
		DP2[i]=dp[i][0];
	}
	dfs3(1);
	for (int i=0;i<=3;++i) T[i].build(1,1,n,i);
	T2.build(1,1,n);
	for (int qt=1;qt<=m;++qt)
	{
		opt=read();
		if (opt==1)
		{
			x=read(),y=read(),k=read(),d=read(),sp=get_path(x,y,k);
			for (int i=0;i<sp.size();++i) T2.add(1,sp[i].l,sp[i].r,d);
		}
		else if (opt==2)
		{
			x=read(),d=read(),sp=DP2[x];
			for (int i=0;i<sp.size();++i) T2.add(1,sp[i].l,sp[i].r,d);
		}
		else if (opt==3)
		{
			x=read(),y=read(),k=read(),sp=get_path(x,y,k),ans=0;
			for (int i=0;i<sp.size();++i) ans+=T2.query(1,sp[i].l,sp[i].r);
			printf("%llu\n",(unsigned long long)(ans));
		}
		else
		{
			x=read(),sp=DP2[x],ans=0;
			for (int i=0;i<sp.size();++i) ans+=T2.query(1,sp[i].l,sp[i].r);
			printf("%llu\n",(unsigned long long)(ans));
		}
	}
	return 0;
}

详细

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 10
Accepted
time: 69ms
memory: 181224kb

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:

37227703492
2136305359188
2794367845468
1309925069860
1698169768858
2678958746332
6690595071246
2087826052960
5786332239171
2186592622
4014965079076
1674542130
6524658548
7094033144666
10065416610040
11589693473717
492570862
3356228199498
2834694279
4198036633070
4395772262
4221137767
9630829210
992...

result:

ok 2559 numbers

Test #2:

score: 0
Runtime Error

input:

5000 5000
54 2
1945 3
4131 4
1207 5
3558 6
3582 7
1648 8
3498 9
1761 10
360 11
3617 12
4359 13
158 14
2314 15
529 16
4619 17
1070 18
1504 19
2675 20
2981 21
2142 22
1349 23
1640 24
1374 25
4059 26
2511 27
2708 28
2939 29
3017 30
3320 31
4602 32
4779 33
2697 34
3906 35
1121 36
197 37
1551 38
1119 39
...

output:


result:


Subtask #2:

score: 0
Runtime Error

Test #3:

score: 0
Runtime Error

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:


result:


Subtask #3:

score: 5
Accepted

Test #5:

score: 5
Accepted
time: 955ms
memory: 382776kb

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
134315201201061
38210069287857
75889674481730
25202765567748
179527420359031
75824479907233
156951577189979
246509811214535
251383387317167
181645886595511
285463150681348
213797241401335
244909583142805
53376921005282
451665818220
379334117147250
720759810155057
768646965102274
224741692238593
18...

result:

ok 100065 numbers

Test #6:

score: 5
Accepted
time: 898ms
memory: 382580kb

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
1950387013442
2906443199266
2144858813468
3137341049831
1081425884175
20924388962208
73530126133368
136609133052209
125022026678010
22502893517249
99022896674514
84010333777754
13909990392191
43442491331837
190816082733002
92810414504491
244006706308139
42843404030538
126151201042579
7249812065288...

result:

ok 99740 numbers

Subtask #4:

score: 0
Runtime Error

Test #7:

score: 0
Runtime Error

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:


Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #4:

0%

Subtask #7:

score: 0
Skipped

Dependency #2:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

0%