QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#461531#6340. TourismRafi22#7 93ms20716kbC++202.7kb2024-07-02 19:58:092024-07-02 19:58:09

Judging History

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

  • [2024-07-02 19:58:09]
  • 评测
  • 测评结果:7
  • 用时:93ms
  • 内存:20716kb
  • [2024-07-02 19:58:09]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif


#define ll long long
#define pb push_back
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define ROF(i,r,l) for(int i=(r);i>=(l);i--)
#define endl '\n'
int inf=1000000007;
ll infl=1000000000000000007;
ll mod=998244353;

const int N=100007,S=300,pot=1<<17;


int seg[2*pot+7];
int seg1[2*pot+7];

int que(int v,int a,int b,int l,int r)
{
	if(a<=l&&b>=r) return seg[v];
	if(r<a||l>b) return inf;
	return min(que(2*v,a,b,l,(l+r)/2),que(2*v+1,a,b,(l+r)/2+1,r));
}
int que1(int v,int a,int b,int l,int r)
{
	if(a<=l&&b>=r) return seg1[v];
	if(r<a||l>b) return -inf;
	return max(que1(2*v,a,b,l,(l+r)/2),que1(2*v+1,a,b,(l+r)/2+1,r));
}

vector<pair<int,int>>W[N];


struct Z
{
	int l,r,i;
};

bool cmp(Z a,Z b)
{
	if(a.l/S==b.l/S) return a.r<b.r;
	else return a.l<b.l;
}

vector<int>G[N];
int O[N];
int ile[N];
int c[N];
int res[N];
int pre[N],post[N],cc;

void dfs(int v,int o)
{
	pre[v]=++cc;
	O[v]=o;
	for(auto u:G[v])
	{
		if(u==o) continue;
		dfs(u,v);
	}
	post[v]=cc;
}

int ans;

void add(int v)
{
	while(v!=0)
	{
		ile[v]++;
		if(ile[v]==1) ans++;
		v=O[v];
	}
}

void del(int v)
{
	while(v!=0)
	{
		ile[v]--;
		if(ile[v]==0) ans--;
		v=O[v];
	}
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m,q;
	cin>>n>>m>>q;
	FOR(i,1,n-1)
	{
		int a,b;
		cin>>a>>b;
		G[a].pb(b);
		G[b].pb(a);
	}
	dfs(1,0);
	for(int i=1;i<=2*pot;i++)
	{
		seg[i]=inf;
		seg1[i]=-inf;
	}
	for(int i=1;i<=m;i++)
	{
		cin>>c[i];
		seg[i+pot-1]=pre[c[i]];
		seg1[i+pot-1]=pre[c[i]];
	}
	for(int i=pot-1;i>0;i--)
	{
		seg[i]=min(seg[2*i],seg[2*i+1]);
		seg1[i]=max(seg1[2*i],seg1[2*i+1]);
	}
	vector<Z>Q;
	for(int i=1;i<=q;i++)
	{
		int l,r;
		cin>>l>>r;
		Q.pb({l,r,i});
		int L=que(1,l,r,1,pot),R=que1(1,l,r,1,pot);
		cout<<R-L+1<<endl;
		//W[L].pb({R,i});
	}
	/*sort(all(Q),cmp);
	int L=0,R=0;
	for(auto x:Q)
	{
		while(L<x.l)
		{
			del(c[L]);
			L++;
		}
		while(L>x.l)
		{
			L--;
			add(c[L]);
		}
		while(R>x.r)
		{
			del(c[R]);
			R--;
		}
		while(R<x.r)
		{
			R++;
			add(c[R]);
		}
		res[x.i]=ans;
	}
	for(int i=1;i<=n;i++)
	{
		
	}
	for(int i=1;i<=q;i++) cout<<res[i]<<endl;*/
	
	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: 2ms
memory: 7224kb

input:

166 249 224
158 52
52 82
158 36
117 158
119 117
5 82
158 18
22 36
82 143
105 36
22 152
36 92
117 2
123 158
5 134
119 89
31 119
92 48
105 149
149 17
108 31
134 50
3 52
63 158
3 51
42 22
17 10
103 158
50 122
92 85
50 78
117 159
36 20
143 115
158 83
20 4
142 22
23 3
96 10
19 134
8 10
151 92
65 108
89 5...

output:

160
165
164
163
163
165
165
149
165
165
163
165
164
163
90
163
161
163
165
156
165
165
160
154
111
125
160
164
159
165
163
165
160
153
160
165
165
163
163
163
165
163
160
165
160
165
165
160
160
153
163
164
153
131
164
165
137
163
165
124
160
165
163
165
89
163
164
165
154
165
165
165
165
121
163
16...

result:

wrong answer 1st numbers differ - expected: '67', found: '160'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 7
Accepted

Test #56:

score: 7
Accepted
time: 63ms
memory: 15216kb

input:

55321 88650 75523
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...

output:

55319
55319
55313
55306
55319
53676
55320
55301
55319
55319
55268
55319
55318
55320
55311
55311
55319
55275
55301
55319
55319
55317
55320
55319
55319
55318
55295
55318
55319
55319
55319
55248
55319
55320
55319
55319
55319
55319
55319
55319
55320
55301
55319
55186
55204
55320
55319
55319
55297
55318
...

result:

ok 75523 numbers

Test #57:

score: 0
Accepted
time: 43ms
memory: 17432kb

input:

80807 56552 65576
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...

output:

80782
80805
80805
80769
80805
80805
80805
80791
80805
80782
80805
80805
80783
80805
80802
80805
80334
80791
80777
80805
80805
80802
80805
80805
80805
80805
80805
80758
80805
80789
80805
80790
80805
80805
80805
80805
80781
80777
80805
80805
80805
80805
80802
80805
80805
80805
80805
80777
80777
80805
...

result:

ok 65576 numbers

Test #58:

score: 0
Accepted
time: 47ms
memory: 18668kb

input:

91904 82063 54619
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...

output:

91904
91883
91878
91896
91897
91902
91902
91901
91748
91902
91904
91904
91901
91904
91896
91904
91896
91901
91901
91904
91900
91886
91902
91904
91894
91902
91853
91885
91893
91893
91902
91900
91902
91886
91902
91904
91416
91904
91901
91904
91904
91902
91904
91904
91902
91904
91828
91809
91904
91875
...

result:

ok 54619 numbers

Test #59:

score: 0
Accepted
time: 92ms
memory: 20216kb

input:

100000 100000 100000
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:

99999
99954
99991
99993
99986
99942
99993
99986
99994
99993
99993
99993
99989
99986
99999
99991
99994
99956
99999
99989
99991
99999
99991
99981
99973
99993
99999
99983
99986
99991
99986
99999
99988
99954
99983
99999
99983
99993
99999
99993
99986
99991
99999
99999
99999
99991
99993
99993
99837
99990
...

result:

ok 100000 numbers

Test #60:

score: 0
Accepted
time: 83ms
memory: 20264kb

input:

100000 100000 100000
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:

100000
99997
99998
99992
99992
99970
99996
99981
99981
99997
99982
99981
99990
99973
99963
99997
99997
99537
99997
99990
99997
99997
99990
100000
99997
99987
99943
100000
99981
99981
99996
99960
99998
99997
100000
99991
99754
99961
99960
99990
99990
100000
99997
99963
99981
99935
99991
100000
99997
...

result:

ok 100000 numbers

Test #61:

score: 0
Accepted
time: 86ms
memory: 19860kb

input:

100000 100000 100000
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:

99996
99998
99998
99998
99994
99915
99996
99972
99996
99998
99998
99837
99996
99998
99996
99994
99989
99942
99998
99603
99998
99972
99981
99915
99463
99994
99994
99994
99996
99969
99972
99989
99998
99989
99998
99603
99843
99959
99998
99998
99998
99996
99998
99998
99996
99998
99996
99998
99994
99998
...

result:

ok 100000 numbers

Test #62:

score: 0
Accepted
time: 93ms
memory: 20716kb

input:

100000 100000 100000
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:

99997
99994
99951
99998
99994
99998
99990
100000
100000
100000
99996
100000
99994
99980
99998
99990
99967
99994
100000
100000
99998
99997
99994
99991
100000
100000
100000
99970
100000
99997
99998
100000
99998
99994
99997
99981
99994
99982
99997
100000
100000
99997
99998
99997
100000
100000
99997
100...

result:

ok 100000 numbers

Test #63:

score: 0
Accepted
time: 89ms
memory: 18908kb

input:

100000 100000 100000
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:

99995
99990
99997
99999
99999
99999
99999
99999
99997
99971
99969
99999
99999
99997
99999
99999
99999
99990
99999
99999
99990
99999
99997
99999
99999
99999
99999
99999
99999
99894
99999
99913
99999
99999
99973
99999
99986
99999
99999
99999
99997
99999
99990
99989
99990
99999
99999
99999
99997
99990
...

result:

ok 100000 numbers

Test #64:

score: 0
Accepted
time: 78ms
memory: 19776kb

input:

100000 100000 100000
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:

99720
99788
99790
99720
99916
99714
99738
99834
99815
99707
99944
99584
99856
99930
99916
99856
99982
99796
99627
99754
99782
99790
99788
99848
99627
99982
99834
99834
99751
99944
99728
99751
99817
99944
99796
99720
99831
99916
99831
99728
99707
99627
99859
99668
99848
99771
99710
99710
99728
99838
...

result:

ok 100000 numbers

Test #65:

score: 0
Accepted
time: 80ms
memory: 19776kb

input:

100000 100000 100000
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:

99649
99852
99852
99852
99632
99758
99761
99820
99730
99750
99887
99783
99721
99865
99802
99867
99798
99811
99553
99691
99852
99750
99787
99774
99948
99774
99695
99811
99649
99811
99908
99975
99806
99761
99760
99820
99862
99806
99903
99798
99783
99691
99811
99903
99908
99865
99811
99632
99750
99948
...

result:

ok 100000 numbers

Test #66:

score: 0
Accepted
time: 71ms
memory: 20496kb

input:

100000 100000 100000
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:

99753
99961
99806
99756
99720
99900
99749
99823
99720
99846
99756
99602
99950
99749
99841
99818
99558
99792
99762
99900
99719
99750
99756
99856
99756
99950
99728
99934
99884
99660
99706
99762
99884
99977
99793
99860
99756
99602
99770
99833
99764
99841
99558
99937
99756
99950
99950
99756
99910
99729
...

result:

ok 100000 numbers

Test #67:

score: 0
Accepted
time: 42ms
memory: 20116kb

input:

100000 1 100000
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
5...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 numbers

Test #68:

score: 0
Accepted
time: 64ms
memory: 19004kb

input:

100000 100000 100000
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:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 numbers

Subtask #4:

score: 0
Wrong Answer

Test #69:

score: 0
Wrong Answer
time: 10ms
memory: 10808kb

input:

54738 54525 1797
45211 4527
4527 43609
4527 19876
16325 43609
32183 4527
16325 32579
43609 25554
32183 38972
45211 53953
16325 19810
10881 19810
45211 12698
27967 19810
25554 46338
51894 45211
25388 16325
512 25554
43609 7820
10206 512
30021 32183
48647 43609
46338 44138
16766 7820
10023 53953
19810...

output:

53547
52464
47444
48219
52115
51607
50507
50757
45996
51680
48315
52427
49252
50917
49910
54047
44117
50193
52500
52171
52410
52517
52072
53601
53750
47940
49907
50195
53693
53403
48444
42297
50311
50726
54008
52172
53202
48951
51928
51683
52725
52842
45986
52387
51049
49844
53454
52365
52972
52561
...

result:

wrong answer 1st numbers differ - expected: '276', found: '53547'

Subtask #5:

score: 0
Wrong Answer

Test #102:

score: 0
Wrong Answer
time: 77ms
memory: 12944kb

input:

55965 89652 95687
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...

output:

55965
55897
55964
55965
55965
55965
55874
55964
55944
55945
55965
55965
55965
55965
55965
55962
55965
55965
55965
55965
55964
55962
55961
55964
55965
55962
55964
55963
55958
55965
55965
55958
55965
55952
55940
55965
55965
55965
55965
55964
55965
55964
55964
55964
55958
55956
55964
55965
55964
55965
...

result:

wrong answer 1st numbers differ - expected: '42788', found: '55965'

Subtask #6:

score: 0
Skipped

Dependency #1:

0%