QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#107055#5020. 举办乘凉州喵,举办乘凉州谢谢喵275307894a0 966ms30688kbC++142.2kb2023-05-20 10:13:052023-05-20 10:13:08

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-20 10:13:08]
  • 评测
  • 测评结果:0
  • 用时:966ms
  • 内存:30688kb
  • [2023-05-20 10:13:05]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
#define fi first
#define se second
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using LL=__int128;
using namespace std;const int N=2e5+5,M=N*4+5,K=20,mod=1e4+7,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(263082);
int n,q,x,y,z,fa[N],Sn[N],Si[N],d[N],Tp[N],ans[N];vector<int> S[N];
void dfs1(int x,int La){fa[x]=La;Si[x]=1;d[x]=d[La]+1;for(int i:S[x]) if(i^La) dfs1(i,x),Si[x]+=Si[i],Si[Sn[x]]<Si[i]&&(Sn[x]=i);}
void dfs2(int x,int La){Tp[x]=La;if(Sn[x]) dfs2(Sn[x],Sn[x]);for(int i:S[x]) if(i^fa[x]&&i^Sn[x]) dfs2(i,i);}
int LCA(int x,int y){while(Tp[x]^Tp[y]) d[Tp[x]]<d[Tp[y]]&&(swap(x,y),0),x=fa[Tp[x]];return d[x]<d[y]?x:y;}
struct BIT{
	int f[N];void Add(int x,int y){while(x<=n) f[x]+=y,x+=x&-x;}int Qry(int x){int Ans=0;while(x) Ans+=f[x],x-=x&-x;return Ans;}
}f1,f2,g;
vector<pair<int,int> > QQ[N];
namespace Part1{
	int vis[N],Si[N],Ct,Rt,f[N];
	void GI(int x,int La){Si[x]=1;Ct++;for(int i:S[x]) if(i^La&&!vis[i]) GI(i,x),Si[x]+=Si[i];}
	void DP(int x,int La){f[x]=Ct-Si[x];for(int i:S[x]) if(i^La&&!vis[i]) f[x]=max(f[x],Si[i]);if(f[x]<f[Rt]) Rt=x;}
	void Ins(int x,int La,int d,int w){g.Add(d+1,w);for(int i:S[x]) if(i^La&&!vis[i]) Ins(i,x,d+1,w);}
	void Qry(int x,int La,int d){
		for(auto i:QQ[x]) if(d<=i.fi) ans[i.se]+=g.Qry(i.fi-d+1);
		for(int i:S[x]) if(i^La&&!vis[i]) Qry(i,x,d+1);
	}
	void Solve(int x){
		Ct=0;GI(x,0);f[Rt=0]=INF;DP(x,0);vis[x=Rt]=1;
		Ins(x,0,0,1);for(auto i:QQ[x]) ans[i.se]+=g.Qry(i.fi+1);
		for(int i:S[x]) if(!vis[i]) Ins(i,x,1,-1),Qry(i,x,1),Ins(i,x,1,1);
		Ins(x,0,0,-1);for(int i:S[x]) if(!vis[i]) Solve(i);
	}
}
int main(){
	int i,j;scanf("%d",&n);for(i=1;i<n;i++) scanf("%d%d",&x,&y),S[x].PB(y),S[y].PB(x);
	dfs1(1,0);dfs2(1,1);scanf("%d",&q);for(i=1;i<=q;i++){
		scanf("%d%d%d",&x,&y,&z);int Ls=LCA(x,y);QQ[Ls].PB({z,i});
	}
	Part1::Solve(1);
	for(i=1;i<=q;i++) printf("%d\n",ans[i]);
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 9ms
memory: 13424kb

input:

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

output:

2546
1004
4981
59
57
3369
3369
1004
4974
1719
59
171
4515
59
4952
4981
4974
1365
4981
1
1004
4780
4974
4974
1
13
4952
4515
59
4864
215
3369
472
1004
59
2546
472
131
13
4780
2546
13
13
4056
4952
171
4780
4974
13
171
13
59
59
1004
4981
3369
13
2546
57
13
4864
171
4952
59
4515
2087
1
4958
9
4056
3369
1...

result:

wrong answer 1st numbers differ - expected: '3226', found: '2546'

Subtask #2:

score: 0
Time Limit Exceeded

Test #9:

score: 8
Accepted
time: 966ms
memory: 30688kb

input:

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

output:

757
69428
2793
181264
91707
182
32496
199183
6399
15975
11640
119051
236
689
15
9532
41
36592
178936
56
45424
193403
90248
3417
949
68
34133
60471
199861
188090
75088
127
1
6
4
3
3
11
61157
199860
199153
155706
196287
192862
53742
51862
179199
428
196282
199989
3613
26
99007
134461
198159
20382
7518...

result:

ok 199996 numbers

Test #10:

score: 0
Accepted
time: 608ms
memory: 30136kb

input:

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

output:

22
31743
62
30
510
6079
94
24063
190
4079
382
30
62
12159
1022
2043
8063
62
4
3063
4079
30
254
46
10
22
6111
12159
16127
22
1
12031
1
94
382
766
4063
254
46
766
1022
62
766
1
22
46
30
8063
8063
254
3063
22
62
30
1
62
254
4
10
15871
1022
46
2039
6079
22
254
1022
16127
30
766
8127
14
14
10
46
1
62
406...

result:

ok 199995 numbers

Test #11:

score: -8
Time Limit Exceeded

input:

199993
25163 125238
125238 19096
19096 88864
88864 113505
113505 12722
12722 56225
56225 8736
8736 74926
74926 38529
38529 80231
80231 19719
19719 198784
198784 75213
75213 190174
190174 163340
163340 62363
62363 144160
144160 130912
130912 3919
3919 21218
21218 85281
85281 187312
187312 79930
79930...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 861ms
memory: 27836kb

input:

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

output:

12
100250
189419
1417
83887
199124
1908
83887
17
4321
12
6
71
199516
1
181342
71
197305
197305
4321
169235
192649
20
189419
77114
71
195121
170566
109022
100
199516
86
12
194525
354
14548
109022
199516
354
152872
169235
197305
10704
38072
54937
181342
100250
71
11
354
181342
132537
10574
181342
1995...

result:

wrong answer 1st numbers differ - expected: '78', found: '12'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%