QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#419789	#8591. Shops	UmairAhmadMIrza^#	24	441ms	60728kb	C++17	909b	2024-05-24 11:16:48	2024-05-24 11:16:50

Judging History

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

[2024-05-24 11:16:50]
评测

测评结果：24
用时：441ms
内存：60728kb

查看

[2024-05-24 11:16:48]
提交

answer

#include <bits/stdc++.h>
using namespace std;

#define ll long long
int const N=5e5+5;
int const mod=1e9+7;

vector<array<int,3>> edges;
vector<int> com[N];
int rep[N];
bool shop[N];
int ans=0;
int main(){
	int n,m;
	cin>>n>>m;
	for (int i = 0; i < m; ++i)
	{
		int u,v,w;
		cin>>u>>v>>w;
		edges.push_back({w,u,v});
	}
	sort(edges.begin(), edges.end());
	for(int i=1;i<=n;i++){
		rep[i]=i;
		com[i].push_back(i);
	}
	for(auto ed:edges){
		int u=ed[1],v=ed[2],w=ed[0];
		if(rep[u]==rep[v])
			continue;
		if(com[rep[u]].size()<com[rep[v]].size())
			swap(u,v);
		if(shop[u]==shop[v])
			for(auto i:com[rep[v]])
				shop[i]^=1;
		u=rep[u];
		v=rep[v];
		for(auto i:com[v]){
			rep[i]=u;
			com[u].push_back(i);
		}
		com[v].clear();
		ans=max(ans,w);
	}
	cout<<ans<<endl;
	string ans="BD";
	for(int i=1;i<=n;i++)
		cout<<ans[shop[i]];
	cout<<endl;
	return 0;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 7

Accepted

time: 0ms

memory: 16940kb

input:

output:

2
BBD

result:

ok inconveniences = 2

Test #2:

score: 0

Accepted

time: 0ms

memory: 15772kb

input:

output:

9
BBDDB

result:

ok inconveniences = 9

Test #3:

score: -7

Wrong Answer

time: 71ms

memory: 18480kb

input:

8 135737
1 4 763713071
3 7 45141437
4 8 618418466
6 8 91803956
7 5 972595945
5 2 751163228
2 8 9886315
4 3 106470622
8 6 949495949
1 2 885918825
4 6 322040168
7 6 754489330
4 8 618968328
5 3 996860159
3 6 210132897
3 4 591744987
8 7 447985622
2 4 4833956
5 7 610154418
2 5 410116873
2 5 912717336
8 7...

output:

47935
BBDDBDDD

result:

wrong answer your claimed answer is 47935, but the inconveniences of your plan is actually 19258

Subtask #2:

score: 0

Wrong Answer

Test #11:

score: 0

Wrong Answer

time: 441ms

memory: 60728kb

input:

500000 499999
1 2 776715136
2 3 406881694
3 4 265792290
4 5 507607272
5 6 182246639
6 7 997847597
7 8 164130256
8 9 278962226
9 10 411194641
10 11 363646402
11 12 672225656
12 13 494629089
13 14 717664153
14 15 121619271
15 16 476857704
16 17 301215244
17 18 810217743
18 19 850722975
19 20 10710274
...

output:

999999116
BDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBD...

result:

wrong answer your claimed answer is 999999116, but the inconveniences of your plan is actually 998789691

Subtask #3:

score: 0

Skipped

Dependency #2:

Subtask #4:

score: 24

Accepted

Test #31:

score: 24

Accepted

time: 266ms

memory: 39516kb

input:

366489 397001
2 127909 1
7 171229 1
8 158597 1
11 282213 1
14 356007 1
15 286102 1
16 93205 1
17 260111 1
18 138962 1
20 359938 1
29 223905 1
31 357684 1
32 259968 1
34 65205 1
37 200276 1
41 83195 1
43 159858 1
48 332277 1
50 320322 1
51 338467 1
53 262785 1
55 83815 1
56 173198 1
58 169473 1
63 19...

output:

1
DDBBBBDBDBBBBDDDBBBBBDBBDDDDBBDDBBDBBBBBBDBBBBBDBBBBBDDDDBBDBBDDDDBBBBBBDDDBDDDBBBDDDDBDDDDBBBBDDBBBBDBDDDBBDBDBDBBBBDBDDBDDBDBBBDBBBDDBBDDDBBBDDBDBDDBDDDBDBDBBDBDBDBDBDBBDDBDBBDBBBBDBBBDDDBBDDDDDDDDDDDDBBBBDBDBDBBBBDDDBBBBDBDBDBDBDDDDBBBBBDDDBBBBDBBBDBBDBBDDDDBBDBDBDBDBDBBDBDDBBDDDBBDDBDDBBDDBDBB...

result:

ok inconveniences = 1

Test #32:

score: 0

Accepted

time: 338ms

memory: 45180kb

input:

475552 488952
2 161263 1
3 312211 1
5 41910 1
6 421865 1
7 340911 1
9 419906 1
10 468773 1
13 17837 1
18 465833 1
19 297766 1
21 234125 1
26 218984 1
28 296050 1
29 411520 1
30 38207 1
33 370786 1
34 21620 1
35 467168 1
40 136766 1
42 353240 1
44 194443 1
46 119022 1
48 23233 1
54 380603 1
60 99339 ...

output:

1
BBDDBDBDDDBBDBBBBDDBDDDDDBDBBBBBDBDDDBDDBDDDBBDDDBBBBBBDBBDBDBDBBBDDBBBDDDDDDDBDBBDDDDDBBBBBDBDBBBDDBBDBBDDBDBDDDDDDBBBBDDDDBDDDDDBBBBDDBBDDBDDBDBDDDDDBDBDDBBDBBBDDDBDBDBBDBBBDBDBBBDBBBBDBBBBDBDBDDBBBDDBDBDBBDDDBDBDDBBBBBBDDBDBDDBBDBBBDDDDBBDBDDBDDDDBDBDBDBBDBBBBBDBDDBDBDDDDBDBBDBBDDBBBDBBBDBDBDDB...

result:

ok inconveniences = 1

Test #33:

score: 0

Accepted

time: 83ms

memory: 25672kb

input:

128817 140020
2 53427 1
5 86824 1
6 33490 1
11 63864 1
14 109608 1
15 12909 1
16 45790 1
19 27271 1
22 54044 1
24 11063 1
32 53692 1
35 70034 1
38 84224 1
39 64068 1
43 72895 1
44 51948 1
45 40428 1
49 127824 1
50 52852 1
60 25795 1
61 105666 1
65 41013 1
67 97450 1
69 49349 1
71 47569 1
72 70751 1
...

output:

1
BBDBBDDDDBBBBDBBBDDBBBBBDDDDBBBBBBDBDBDBBBDDBBBBBBBDDDBBBDDDBDDBDDBDBBBBDDDDDDDDBDDBDBBDDBBBDBBBDBDBDBBBBBDDDDBDDBBBDBBDBDDBDDBBDDDBBDDDDBBDBDBBBBBBBBDDDDDDBDDBBDDBBBDBBBBDDDBDBBBDBBDDDDBDBBBBDDDBBDDBBBBDDDDBBDBDDDDDDDDDDBDBBDBDDDBBDBDDBBBDDDBBDDBBDDBBBBBBBDDBBBBBDDBBDDBBBDDBDBDBDBDBDDDBBDDDDDBDDD...

result:

ok inconveniences = 1

Test #34:

score: 0

Accepted

time: 219ms

memory: 36260kb

input:

299635 331829
5 197808 1
11 67054 1
12 84275 1
15 287112 1
16 274955 1
24 40825 1
30 266299 1
34 81379 1
35 99815 1
38 219853 1
42 189961 1
47 107895 1
48 137516 1
50 80614 1
54 264232 1
55 93625 1
62 143056 1
63 70844 1
64 72811 1
65 164091 1
68 248158 1
70 9821 1
72 156352 1
77 215022 1
81 270025 ...

output:

1
DDBDDDBDBDDBBDDDDDBDBBBBDDDBBDBBDBBBBBBBBBDDBDDDBDBBDDDBDDDDDDDDBDBDBDBBDBBBBDBDBBDBBBDBDBDBDDBDDDDDDBDDDDBDDDBBBBDBBDBBDBBDDBDBBDDBDBDDBBDBDDBBBBBDDBDBBBDBBBBBDDDBDBDDBDBBDDDDBBDDDBDBDBDBDBDDDBBDDBDBDBBBDBBBDDBDDDDDBBDDBDDBBBBDBDDDBBDBDBBDDBBDDDDBDBDDDBBDDDDDBDBBBBBDBBDDDBDDBBBBBBBBBDBDDDBDBDDDBB...

result:

ok inconveniences = 1

Test #35:

score: 0

Accepted

time: 314ms

memory: 38852kb

input:

369927 447544
1 150509 1
5 250257 1
6 149327 1
7 201307 1
15 330381 1
16 158914 1
18 99391 1
24 90164 1
25 199087 1
28 306199 1
32 83429 1
35 212184 1
36 29977 1
37 261629 1
44 99341 1
45 48378 1
51 130523 1
53 148929 1
58 77382 1
71 211093 1
72 305907 1
73 227420 1
75 188876 1
76 71437 1
79 354402 ...

output:

1
BDBDDDBDBBBDBBBDBDDBBDBDBDDBBBDBDBBBBBBDDBBDDBBDBDBBDDBBBBDDDDDDDDDBBBDBBDBDDDBDDBDDDDBDDBBDBBBBBDBDDBDBBBBBDBBBDBDBBBDBDBDDDDDBDDDDBDBDBBBDBDBBBBDDDDBBBDBBBDDBBDDDBDDBBBBBBDBDDDDBDDDDBDBBDDBBDDDBBDDBBDDDBDBBDDDDDDDBDBDDDBDDBBDBDDBBDDBDDBDBDDDDBBDDDDDDBDDDBDBDDBBBBBDBBDDDDBDDDDDBDBBDBDBDBDDBDBDDDB...

result:

ok inconveniences = 1

Test #36:

score: 0

Accepted

time: 338ms

memory: 52064kb

input:

500000 500000
4 319400 1
12 186157 1
13 443669 1
15 227339 1
19 101284 1
20 183604 1
23 273179 1
26 236933 1
27 79090 1
28 826 1
29 7574 1
31 370188 1
32 48463 1
34 113530 1
35 209157 1
46 13739 1
47 188127 1
48 97203 1
51 251724 1
52 469749 1
53 451782 1
56 249224 1
58 262324 1
60 380990 1
61 82320...

output:

1
DDDDDDDBDDBDDDDBDBBBDDBBDDDBDBDDBBBBDDDDBDDDBBBDBDDBBDBBDBDBDDDBBBDBDBBDDBDBDBBDBBDBBDBBBDBDDDDDDDBDBBDDBDDBDDBDBBDDDDDBDBDBBBDDDBBDBDBBBDBBDDDDDBBDBDBBDBBDBDDDBBBBDDDDDDDBBDBBBBBDBDDDBDDDBBBDDDBBDBDDDDBBDDBBDBDDBDBDDDBDBBDBBBDDBDBBBDBBBBDBBDDBBDDDDDBDDDBDBDBDBBBDDDBBDDDDBBDBBDBBBBBDBDBBDDBDDBDBDB...

result:

ok inconveniences = 1

Test #37:

score: 0

Accepted

time: 349ms

memory: 53540kb

input:

500000 500000
2 182927 1
5 313016 1
9 438269 1
10 97892 1
11 373266 1
13 314494 1
14 318813 1
20 102513 1
23 304478 1
24 162451 1
27 207273 1
30 182950 1
34 133161 1
35 62401 1
37 102023 1
38 19183 1
41 96619 1
42 264471 1
45 339682 1
46 60188 1
51 134306 1
53 85702 1
54 170539 1
55 74017 1
73 14900...

output:

1
BBDDDBBBBBDBBBDBDBBDDBBBBBBBDBDDBDDBBDDDBDBDBDDDDBDDBBBBDBBBDDDBBBDBDBDBBDBBDDBDDDBDBDBBDDBBDBBBDDDDBDDDDDBDDDDDDDBDBBBDBBBDBBDBDDBBDBDDDDBDBBDDDBDDBBBDBBBDDBBBDDDDDBDDDBDBBBDBBDDDBBBBDBDBBDBDBDDBDBDBDDBDBBDDBDBBDDDDBDBDBDDBBDDBDBBBBDBBDDDDBBBDDDBDDDBBBDBDBDDDDDBBBBBDBDBBDBDBDBBBDDBBDDDDDBBDBDBDDD...

result:

ok inconveniences = 1

Test #38:

score: 0

Accepted

time: 363ms

memory: 52556kb

input:

500000 500000
4 490349 1
5 377743 1
7 261998 1
14 410844 1
17 106150 1
20 477772 1
22 48037 1
24 388329 1
26 328805 1
28 248860 1
30 216330 1
34 479575 1
37 303722 1
38 392533 1
40 191119 1
42 177919 1
44 322555 1
45 306160 1
50 129452 1
51 215260 1
53 146880 1
56 441549 1
64 249852 1
69 422318 1
70...

output:

1
BDDDBDBDDBBDDDBDDDBDDBBBDBDDBBDBBDBBDBBDDBBBDDBBDDBBBBDDBBDBDDBDDBDBDDDDBBBDDDBDBBDDBDBBDDBDDBBDBDDBDDDBBBDBBDDDBDBBBDDBBBDBDBDDBBDDDDBBDBBBBBDDDDBBBDBDDBBDBBBDDDBDBBBDDDDDDDBDBBBBDBDBBBBBBDBDDBDBBBBDBDDDBDBBDDBDDBBBBDDDDDDBDBBBDDBBDBBDBDDDBBDBBBDBBDDBDBBBDDBDDBBBBDDDDDBDDBDBBDBDDDBDDDDDDDDDBDBDDB...

result:

ok inconveniences = 1

Test #39:

score: 0

Accepted

time: 351ms

memory: 53028kb

input:

500000 500000
9 213713 1
13 307012 1
14 327287 1
16 103990 1
23 409412 1
24 80587 1
25 91210 1
26 413674 1
28 167751 1
29 223056 1
31 395367 1
34 70127 1
38 344870 1
39 499865 1
40 91257 1
41 443805 1
43 109678 1
47 387825 1
49 328529 1
53 186674 1
59 197682 1
60 27560 1
61 402852 1
64 380750 1
66 1...

output:

1
DBBBBDDBBBDDBDDBBDDBBBBDBDDDDBDBDDDDBDBDDDBDBDDBBDBBDBDDBDBDDBBDBBBBBDBDBDBDDDDBDBBBDDBBDDDBBDBDDBBBBBDBBDDBBDDBBBBDBBDBDDBDBBDBBDDBBDDDDDBDBDDBDDBDDDBBDBDDDDBBBDBBBBDBBBDDBDBBDDBBBBBDBDBBBBBDDBDBBDDBBBBDDBBBBBBBBBDDDDDDBDBBBDBDDBDBBDDDDDDDDBDDBDDDBBBDBBBDBBBDDDDDDDBDBDDDBBBDDBDBBBBDBDBBBBDBBBDBDB...

result:

ok inconveniences = 1

Test #40:

score: 0

Accepted

time: 360ms

memory: 52856kb

input:

500000 500000
1 420147 1
2 70976 1
5 354943 1
6 261427 1
9 317379 1
11 31032 1
15 419781 1
16 155356 1
19 459807 1
25 72438 1
28 385731 1
30 19123 1
34 18208 1
35 332853 1
39 338723 1
41 356728 1
42 114047 1
44 389270 1
47 112208 1
48 23788 1
52 312381 1
57 317756 1
60 311741 1
61 218196 1
62 182171...

output:

1
DBDDBBBBBBDBDBDDDBBBDBBDDBBBDBBDBBDBDDDDBBDBBDBDBDBBDDDDBBDDBBBBBDBBBBDBBBDBDDDDBBBDBDBBBBDDDDDDDDDBDDBDDBDDDDBDBDBDBBDDDDBDDDBDBDBBBBBDBBBDDBBBBBDDDDDBBBBBBDDBDBDDDBDBDBBBBDBBBBDDDDDDDDDDDDDDDDDDDDBBBBBBBBBDDDBDDDBDDDBDDBBBDBDDDDBDBBDDDBDDDBDBBDDDBDDBDDBDDBBDDDBBDDBBBDDBDDBBBDDDDBDBDDDBBDDDBBBBDD...

result:

ok inconveniences = 1

Subtask #5:

score: 0

Skipped

QOJ.ac

QOJ

Judging History

answer

Details

Subtask #1:

Test #1:

input:

output:

result:

Test #2:

input:

output:

result:

Test #3:

input:

output:

result:

Subtask #2:

Test #11:

input:

output:

result:

Subtask #3:

Dependency #2:

Subtask #4:

Test #31:

input:

output:

result:

Test #32:

input:

output:

result:

Test #33:

input:

output:

result:

Test #34:

input:

output:

result:

Test #35:

input:

output:

result:

Test #36:

input:

output:

result:

Test #37:

input:

output:

result:

Test #38:

input:

output:

result:

Test #39:

input:

output:

result:

Test #40:

input:

output:

result:

Subtask #5:

Dependency #1: