QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#178599#6332. Two CurrenciesRNG_Sword_S1130 944ms842960kbC++143.2kb2023-09-14 08:52:452023-09-14 08:52:46

Judging History

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

  • [2023-09-14 08:52:46]
  • 评测
  • 测评结果:30
  • 用时:944ms
  • 内存:842960kb
  • [2023-09-14 08:52:45]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed rt[800010];
pair<int,int> operator+(pair<int,int> x,pair<int,int> y)
{
	return make_pair(x.first+y.first,x.second+y.second);
}
namespace ds1
{
	int t[50000010];
	signed cnt[50000010],ls[50000010],rs[50000010],tot=0;
	void update(signed &x,int l,int r,int p,int v)
	{
		if(!x)
			x=++tot;
		t[x]+=v;cnt[x]++;
		if(l==r)
			return ;
		int mid=(l+r)/2;
		if(p<=mid)
			update(ls[x],l,mid,p,v);
		else
			update(rs[x],mid+1,r,p,v);
	}
	vector<int> cur;
	int query(int l,int r,int k)
	{
		if(l==r)
			return (k/l);
		int lcnt=0,lsum=0,mid=(l+r)/2;
		for(int x:cur)
			lcnt+=cnt[ls[x]],lsum+=t[ls[x]];//cout<<x<<' ';
//		cout<<endl;
		if(lsum<=k)
		{
			for(int &x:cur)
				x=rs[x];
			return query(mid+1,r,k-lsum)+lcnt;
		}
		for(int &x:cur)
			x=ls[x];
		return query(l,mid,k);
	}
};
vector<int> v;
namespace ds2
{
	void insert(int x,int l,int r,int p,int v)
	{
		ds1::update(rt[x],1,1e9,v,v);	
		if(l==r)
			return ;
		int mid=(l+r)/2;
		if(p<=mid)
			insert(x<<1,l,mid,p,v);
		else
			insert(x<<1|1,mid+1,r,p,v);
	}	
	void findit(int x,int l,int r,int ll,int rr)
	{
		if(r<ll||rr<l)
			return ;
		if(ll<=l&&r<=rr)
		{
			v.push_back(rt[x]);
			return ;
		}
		int mid=(l+r)/2;
		findit(x<<1,l,mid,ll,rr);
		findit(x<<1|1,mid+1,r,ll,rr);
	}
};
vector<int> e[200010],id[200010];
int n,m,q;
vector<int> cc[200010];
vector<int> val[200010];
namespace ds3
{
	int fa[200010],sz[200010],dfn[200010],cnt=0;
	int top[200010],mxson[200010],dp[200010];
	int sum[200010];
	void dfs1(int x,int pre)
	{
		fa[x]=pre;sz[x]=1;dp[x]=dp[pre]+1;
		sum[x]=sum[pre]+val[x].size();
		for(int y:e[x])
			if(y!=pre)
			{
				dfs1(y,x),sz[x]+=sz[y];
				if(sz[y]>sz[mxson[x]])
					mxson[x]=y; 
			}
	}
	void dfs2(int x,int pre)
	{
		dfn[x]=++cnt;top[x]=pre;
		for(int y:val[x])
			ds2::insert(1,1,n,dfn[x],y);
		if(mxson[x])
			dfs2(mxson[x],pre);
		for(int y:e[x])
			if(y!=fa[x]&&y!=mxson[x])
				dfs2(y,y);
	}
	int query(int x,int y,int v)
	{
		::v.clear();
		int ans=sum[x]+sum[y];
	//	cout<<ans<<endl;
		while(top[x]!=top[y])
		{
			if(dp[x]<dp[y])
				swap(x,y);
	//		cout<<dfn[top[x]]<<' '<<dfn[x]<<endl;
			ds2::findit(1,1,n,dfn[top[x]],dfn[x]);
			x=fa[top[x]];
		}
		if(dp[x]>dp[y])
			swap(x,y);
	//	cout<<dfn[x]+1<<' '<<dfn[y]<<endl;
		if(x!=y)
			ds2::findit(1,1,n,dfn[x]+1,dfn[y]);
		ans-=2*sum[x];
		ds1::cur=::v; 
	//	cout<<ans<<endl;
		return ans-ds1::query(1,1e9,v);
	}
	void build()
	{
		dfs1(1,0);
		dfs2(1,1);
	}
};
void dfs(int x,int pre)
{
	for(int i=0;i<e[x].size();i++)
	{
		int y=e[x][i];
		if(y==pre)
			continue;
		for(int z:cc[id[x][i]])
			val[y].push_back(z);
		dfs(y,x);
	}
}
signed main()
{
	scanf("%lld%lld%lld",&n,&m,&q);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%lld%lld",&x,&y);
		e[x].push_back(y);id[x].push_back(i);
		e[y].push_back(x);id[y].push_back(i);
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%lld%lld",&x,&y);
		cc[x].push_back(y);
	}
	dfs(1,0);ds3::build();
	while(q--)
	{
		int x,y,a,b;
		scanf("%lld%lld%lld%lld",&x,&y,&a,&b);
		int res=max(ds3::query(x,y,b),0ll);
		if(res<=a)
			printf("%lld\n",a-res);
		else
			puts("-1");
	}
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 12ms
memory: 42832kb

input:

1831 1865 1153
832 1698
1672 1619
634 920
328 1244
571 1279
1673 1815
1098 92
1320 432
244 636
991 1446
308 569
1118 1356
1733 71
497 1679
1699 635
1254 1295
853 345
364 1396
1183 1134
524 1557
1642 1262
1767 459
918 794
1644 539
902 1046
334 1789
1691 1548
1298 520
1763 216
1161 1065
682 1167
1282 ...

output:

378730605
649537044
339843141
362013697
600127619
123276007
749019778
22
21
54569538
-1
26669081
33
255375699
0
7
4
-1
427653834
2
9
17
5
4
-1
8
-1
265022184
218253041
-1
24
849614439
4
29092527
539604026
0
-1
-1
6
-1
12
8
-1
22
-1
13
11
26
7
-1
2
0
546008661
2
6
86261072
-1
448122840
873577464
-1
-...

result:

wrong answer 9th numbers differ - expected: '30', found: '21'

Subtask #2:

score: 0
Wrong Answer

Test #32:

score: 0
Wrong Answer
time: 317ms
memory: 141096kb

input:

99819 89735 60985
59741 24953
61387 12293
53761 1828
60970 60534
40598 48807
21876 21232
29527 13335
84269 40756
89571 12996
25757 40587
52477 63347
41372 69243
16391 58678
40854 39513
84384 91744
62938 60371
81932 45504
34121 54746
51945 14294
883 85344
78845 51797
45025 76590
37694 65493
4118 2588...

output:

36
-1
6
53
-1
-1
652673843
-1
422622756
-1
-1
-1
29
-1
-1
-1
-1
427634455
18
265926271
263974211
877045993
8
288833077
997549690
644774220
16
995218986
31
24
924036742
5
19
2
-1
4
-1
4393606
22
-1
932888431
991013529
8
10
-1
0
-1
19
-1
14
8
502124020
726366843
-1
24
119719836
-1
19
217737158
-1
9415...

result:

wrong answer 3rd numbers differ - expected: '12', found: '6'

Subtask #3:

score: 30
Accepted

Test #59:

score: 30
Accepted
time: 511ms
memory: 574600kb

input:

95629 64841 64314
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:

-1
701714740
-1
610354140
816755067
2440
245932872
-1
29509
866966613
744072492
890
-1
969398264
588051152
381506396
2347
5427
4829
44377
195466300
60823
508
459304253
400544113
-1
787773518
3856
9692
6576
322820913
900985028
1473
14691
26175
-1
27082
-1
9735
3846
537036842
-1
261459575
86658
635912...

result:

ok 64314 numbers

Test #60:

score: 0
Accepted
time: 453ms
memory: 468520kb

input:

92502 51399 68929
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:

36266
-1
-1
112572200
27068354
-1
10394
329233107
444229297
223185833
363055390
1754
14433
-1
4346
-1
33082
457460095
-1
5482
749013593
717085104
5006
-1
926464006
1983
589805099
7590
264497528
8979
903766762
24704
903
923960764
4211
53272133
17012
435443676
-1
984123705
-1
1980
-1
2907
20373
813690...

result:

ok 68929 numbers

Test #61:

score: 0
Accepted
time: 708ms
memory: 729640kb

input:

53810 92751 89379
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:

462043454
6397
31647
98446547
81496
14
34784
1587
532169187
35742
753712897
400460299
299860851
-1
26049
984595650
8185
13794
721579357
166901630
16093
-1
48327
52280
-1
36956
49549
33065
703982006
15511
171757272
130683368
-1
16949
-1
96442497
948433381
-1
-1
-1
3
55603
-1
120939988
12974
952750599...

result:

ok 89379 numbers

Test #62:

score: 0
Accepted
time: 944ms
memory: 842100kb

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:

22357
29573
45104
2184
-1
109258
31337
-1
26387
41578
8392
36172
1160
9470
-1
6923
-1
-1
302
26401
-1
52971
25666
1970
104774
-1
33764
-1
-1
43624
5470
26387
38352
-1
8495
8983
7396
8448
4711
72385
-1
4832
-1
5388
4583
1151
38790
30979
-1
17732
28535
45088
-1
-1
97310
15663
92961
12755
949
-1
22729
...

result:

ok 100000 numbers

Test #63:

score: 0
Accepted
time: 918ms
memory: 842668kb

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:

6483
8781
-1
24456
222
-1
12374
98
41520
29393
-1
12028
17768
6307
74435
24594
11204
16315
48834
4474
4600
27773
-1
60970
14035
-1
-1
24779
-1
43438
18890
33556
-1
12374
-1
94129
30482
14337
40498
-1
57947
-1
44294
49557
-1
-1
9235
9347
-1
38102
23295
102062
10387
-1
25191
107152
7034
71071
-1
-1
-1...

result:

ok 100000 numbers

Test #64:

score: 0
Accepted
time: 899ms
memory: 842960kb

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:

6354
42704
101441
2857
-1
5542
731
16360
9695
3884
-1
27833
3621
2789
57396
17523
-1
-1
44325
575
7390
-1
-1
39509
17011
27425
-1
12285
62336
-1
-1
-1
-1
3146
273
25050
37917
50109
35442
31916
3096
47751
65204
-1
34032
39181
-1
27586
-1
30894
-1
-1
24707
2796
18515
45391
99909
15335
10383
10905
-1
3...

result:

ok 100000 numbers

Test #65:

score: 0
Accepted
time: 927ms
memory: 728708kb

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:

2311
-1
24585
99022
24662
57394
69711
535
27286
32344
2731
9879
-1
27909
49883
1296
14120
40331
40056
-1
-1
12185
19154
16114
-1
277
23779
-1
-1
13181
52941
31439
10184
-1
3425
5039
-1
80057
-1
253
2188
89575
6499
-1
21752
75653
-1
56204
-1
25131
-1
47353
-1
3783
-1
25426
33521
-1
44916
15271
3317
1...

result:

ok 100000 numbers

Test #66:

score: 0
Accepted
time: 846ms
memory: 717924kb

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:

2587
12143
16964
21386
-1
101210
-1
6285
2557
13670
20738
43749
919
53823
4494
98909
-1
65499
670
-1
21401
2009
66503
-1
-1
49535
62266
37556
6535
731
-1
111804
4842
3527
3557
1260
30321
68998
57960
11241
26780
2411
74629
60899
92019
73225
9479
-1
13551
2534
1509
13677
3454
113005
11
-1
3573
9791
-1...

result:

ok 100000 numbers

Test #67:

score: 0
Accepted
time: 935ms
memory: 728268kb

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:

77660
52
106332
14061
3270
105
18174
-1
77805
50254
969
2318
4576
4994
31416
-1
12558
24255
6163
112456
-1
3285
65589
1757
18715
8429
-1
12879
25335
21564
85094
800
-1
6169
7190
696
7335
5834
11350
58406
-1
49158
39385
45499
-1
22975
-1
18130
103
50778
15483
23138
10195
1015
2379
-1
-1
-1
100907
-1
...

result:

ok 100000 numbers

Test #68:

score: 0
Accepted
time: 633ms
memory: 841632kb

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:

8988
-1
14443
-1
9877
566
9580
29456
4906
1691
2002
-1
11435
16258
6720
25040
3685
10643
13471
-1
-1
2122
20594
21629
-1
2249
-1
7575
-1
26840
3457
-1
16212
27410
-1
12628
735
35566
9707
33849
-1
-1
14253
7281
-1
29983
22468
17260
-1
26884
32563
5205
32034
18537
-1
23089
-1
-1
20489
16040
-1
14918
3...

result:

ok 100000 numbers

Test #69:

score: 0
Accepted
time: 576ms
memory: 841692kb

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:

1742
787
2082
1836
-1
-1
1627
5815
-1
4401
4394
3625
1587
-1
-1
-1
4148
-1
-1
8136
6572
5217
1943
2258
-1
3108
3768
4306
-1
4910
-1
133
4849
-1
5841
3316
1800
960
1422
-1
-1
1551
2020
6543
5501
1369
969
2603
7944
-1
1593
2764
1249
-1
3673
2691
2441
-1
-1
525
6117
6052
-1
7356
1396
319
1791
3598
5547...

result:

ok 100000 numbers

Test #70:

score: 0
Accepted
time: 685ms
memory: 840480kb

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:

18837
23143
-1
8074
17906
23043
22447
4474
-1
-1
-1
23669
18990
8666
30486
13797
15263
7816
37953
8640
11509
-1
-1
29212
-1
18317
11521
1666
35408
-1
40547
15656
36307
-1
32990
44551
-1
-1
982
22202
-1
25209
-1
14796
687
3218
30059
2421
6558
7656
2579
-1
-1
-1
46022
-1
18254
38968
24549
19782
-1
144...

result:

ok 100000 numbers

Test #71:

score: 0
Accepted
time: 662ms
memory: 842788kb

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:

17013
-1
41429
-1
9558
14122
4177
2863
6179
10012
18668
-1
22362
-1
7604
1525
-1
1695
21676
9201
14992
11539
13085
5285
125129
9680
7725
-1
2697
7054
-1
-1
12370
2872
14385
-1
11028
-1
4915
10533
19472
8246
-1
19183
-1
8850
-1
9950
-1
-1
12145
3988
4652
8232
-1
1884
63752
-1
18594
14048
9432
1651
79...

result:

ok 100000 numbers

Subtask #4:

score: 0
Skipped

Dependency #1:

0%