QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#768509#7767. 数据结构zhouhuanyi5 621ms343064kbC++146.3kb2024-11-21 11:33:482024-11-21 11:33:49

Judging History

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

  • [2024-11-21 11:33:49]
  • 评测
  • 测评结果:5
  • 用时:621ms
  • 内存:343064kb
  • [2024-11-21 11:33:48]
  • 提交

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)};
}
int n,m,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<reads>dp[N+1][4];
vector<reads>DP[N+1][4];
vector<reads>DP2[N+1];
vector<reads>DWP[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>solve(int l,int r)
{
	if (l==r) return DWP[l];
	int mid=(l+r)>>1;
	return solve(l,mid)+solve(mid+1,r);
}
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)
{
	int y=x;
	vector<int>sp;
	vector<int>tp;
	while (y) dfn[y]=++leng,sp.push_back(y),top[y]=x,rev[dfn[y]]=y,y=hs[y];
	for (int i=0;i<=3;++i)
	{
		tp.clear();
		for (int j=0;j<sp.size();++j)
			if (!num[sp[j]])
			{
				num[sp[j]]=++length;
				for (int k=0;k<ES[sp[j]].size();++k) tp.push_back(ES[sp[j]][k]);
			}
		sp=tp;
	}
	while (y)
	{
		for (int i=0;i<ES[y].size();++i)
			if (ES[y][i]!=hs[y])
				dfs2(ES[y][i]);
		y=hs[y];
	}
	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]);
	}
	if (!ES[x].empty())
	{
		for (int i=0;i<ES[x].size();++i) DWP[i+1]=DP2[ES[x][i]];
		DP2[x]=DP2[x]+solve(1,ES[x].size());
	}
	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;
	vector<int>zp;
	n=read(),m=read();
	for (int i=1;i<=n-1;++i) x=read(),y=read(),add(x,y);
	depth[1]=1,dfs(1),dfs2(1);
	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)
		{
			for (int t=0;t<E[j].size();++t) DWP[t+1]=dp[E[j][t]][i-1];
			if (E[j].empty()) dp[j][i]=dp[j][i-1];
			else dp[j][i]=dp[j][i-1]+solve(1,E[j].size());
		}
	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;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 35ms
memory: 164736kb

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:

0
768923601388
2099590041248
286987402788
752537985644
1930863827318
6227278751095
1747983630208
4234288025924
2186592622
3107678154407
6540025950
7825890790
5062590518238
9178422112172
8484694082565
3710804959
2868904962877
2240142271
6017833058483
4771281709
4221137767
6937447846
0
16124680084935
...

result:

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

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:

0
0
0
2248144434
3054888636
3054888636
3054888636
3054888636
0
0
3512495396
0
0
4827589601
4827589601
0
5612893094
0
0
0
0
0
7003161388
0
9357900481
9357900481
0
9467066357
9467066357
9467066357
0
0
9467066357
9467066357
0
9734067900
0
9734067900
9734067900
0
0
0
10616330938
0
10616330938
0
10616330...

result:


Subtask #3:

score: 5
Accepted

Test #5:

score: 5
Accepted
time: 589ms
memory: 343064kb

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: 621ms
memory: 343036kb

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
Wrong Answer

Test #7:

score: 0
Wrong Answer
time: 401ms
memory: 248256kb

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:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

0%