QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#80101#5403. 树数术tricyzhkx20 982ms327564kbC++142.5kb2023-02-22 08:37:482023-02-22 08:37:50

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-22 08:37:50]
  • 评测
  • 测评结果:20
  • 用时:982ms
  • 内存:327564kb
  • [2023-02-22 08:37:48]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
const int SIZE=(1<<21)+1;
typedef long long ll;
char ibuf[SIZE],obuf[SIZE],*iS,*iT,*oS=obuf,*oT=obuf;
char* flush(){fwrite(obuf,1,oT-oS,stdout);return oT=obuf;}
struct Flusher{~Flusher(){flush();}}flusher;
# define gc() (iS==iT && (iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),iS==iT)?EOF:*iS++)
# define pc(c) ((oT==oS+SIZE && flush()),*oT++=(c))
int read()
{
	int x=0;
	char ch=gc();
	for(;ch<'0' || ch>'9';ch=gc());
	for(;ch>='0' && ch<='9';ch=gc()) x=x*10+ch-'0';
	return x;
}
void write(ll x)
{
	if(x>=10) write(x/10);
	pc(x%10+'0');
}
vector<int> G[700010];
int a[700010],stk[700010],nxt[700010][20],top[20][700010],dep[700010],dfn[700010],sz[700010],opn[700010],minn[21][1400010],tot,tot2;
int Low(int u,int v){return dep[u]<dep[v]?u:v;}
int lca(int u,int v)
{
	u=opn[u];v=opn[v];
	if(u>v) swap(u,v);
	int k=__lg(v-u+1);
	return Low(minn[k][u],minn[k][v-(1<<k)+1]);
}
bool in(int u,int v){return dfn[u]<=dfn[v] && dfn[v]<dfn[u]+sz[u];}
int Top(int l,int r)
{
	int k=__lg(r-l+1);
	return lca(top[k][l],top[k][r-(1<<k)+1]);
}
void dfs(int u,int fa)
{
	sz[u]=1;dfn[u]=++tot;
	opn[u]=++tot2;minn[0][tot2]=u;
	for(int v:G[u])
	{
		if(v==fa) continue;
		dep[v]=dep[u]+1;
		dfs(v,u);sz[u]+=sz[v];
		minn[0][++tot2]=u;
	}
}
int calc(int &u,int l,int r)
{
	int ans=0,p=l;
	if(u && !in(a[p],u))
	{
		for(int i=19;i>=0;i--)
			if(!in(a[nxt[p][i]],u))
				p=nxt[p][i];
		p=nxt[p][0];
	}
	if(p>r) return 0;
	for(int i=19;i>=0;i--)
		if(nxt[p][i]<=r) ans+=1<<i,p=nxt[p][i];
	u=u?lca(u,Top(l,r)):Top(l,r);
	return ans+1;
}
int main()
{
	int n,m,q,u,v;
	n=read();m=read();q=read();
	for(int i=1;i<n;i++)
	{
		u=read();v=read();
		G[u].push_back(v);G[v].push_back(u);
	}
	dfs(1,0);
	for(int i=1;i<=20;i++)
		for(int j=1;j+(1<<i)-1<=tot2;j++)
			minn[i][j]=Low(minn[i-1][j],minn[i-1][j+(1<<(i-1))]);
	for(int i=1;i<=m;i++) a[i]=read();
	int tp=0;
	stk[0]=m+1;nxt[m+1][0]=m+1;
	for(int i=m;i>=1;i--)
	{
		int u=a[i];
		while(tp && !in(a[stk[tp]],u)) u=lca(u,a[stk[tp]]),tp--;
		nxt[i][0]=stk[tp];stk[++tp]=i;
	}
	for(int i=m+1;i>=1;i--)
		for(int j=1;j<=19;j++)
			nxt[i][j]=nxt[nxt[i][j-1]][j-1];
	for(int i=1;i<=m;i++) top[0][i]=a[i];
	for(int i=1;i<=19;i++)
		for(int j=1;j+(1<<i)-1<=m;j++)
			top[i][j]=lca(top[i-1][j],top[i-1][j+(1<<(i-1))]);
	while(q--)
	{
		int k=read(),l,r,u=0;
		ll ans=0;
		while(k--) l=read(),r=read(),ans+=calc(u,l,r);
		write(ans);pc('\n');
	}
	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: 660ms
memory: 327564kb

input:

699990 699995 233333
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...

output:

121987
133434
87432
18265
285143
194269
177810
454211
417130
299450
240901
227736
186417
163975
292497
216139
367014
16634
192685
27351
52127
51646
142169
182616
339876
117003
51132
229206
187647
268093
398455
83905
95731
157096
178338
60211
366172
65279
16903
222331
471095
184145
144524
155389
1407...

result:

wrong answer 2nd lines differ - expected: '139520', found: '133434'

Subtask #2:

score: 20
Accepted

Test #2:

score: 20
Accepted
time: 982ms
memory: 298332kb

input:

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

output:

211594
160846
176729
128251
32662
70710
74884
9095
68282
91324
154262
24279
31878
173468
75265
139715
91660
87525
194302
16875
81535
172911
29145
20483
151883
5255
9548
58890
38076
94152
14358
74859
48870
23981
41390
60976
13795
125823
427
26641
130620
174231
73241
55291
2364
78864
23391
4866
36002
...

result:

ok 699992 lines

Subtask #3:

score: 0
Wrong Answer

Test #3:

score: 0
Wrong Answer
time: 72ms
memory: 57900kb

input:

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

output:

9733
11330
2539
5136
16099
23231
11401
8240
16249
3378
8917
11977
8991
10057
6099
2525
9760
18955
12750
3119
21383
14977
12263
5714
15707
452
533
13254
13883
10446
7035
16796
11009
6434
15761
20419
11157
12192
14327
3733
8967
5239
4114
6407
7340
4697
15415
8747
7057
11878
12023
1218
8380
6371
1802
1...

result:

wrong answer 3rd lines differ - expected: '8403', found: '2539'

Subtask #4:

score: 0
Skipped

Dependency #1:

0%