QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#419752#8591. ShopsFaisal-Saqib#24 369ms63872kbC++172.0kb2024-05-24 10:53:312024-05-24 10:53:33

Judging History

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

  • [2024-05-24 10:53:33]
  • 评测
  • 测评结果：24
  • 用时：369ms
  • 内存：63872kb
查看
  • [2024-05-24 10:53:31]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+10;
int dist[N];
vector<pair<int,int>> ma[N];
bool vis[N];
char ans1[N];
void dfs(int x,char c='B')
{
	vis[x]=1;
	ans1[x]=c;
	if(c=='B')
		c='D';
	else
		c='B';
	for(auto [y,w]:ma[x])
	{
		if(!vis[y])
		{
			dfs(y,c);
		}
	}
}
signed main()
{
	int n,m;
	cin>>n>>m;
	for(int j=0;j<m;j++)
	{
		int x,y,c;
		cin>>x>>y>>c;
		ma[x].push_back({y,c});
		ma[y].push_back({x,c});
	}
	// if(n<=16)
	// {
	// 	// full brute forcess
	// 	int val=1e11;
	// 	string an="";
	// 	for(int mask=0;mask<(1<<n);mask++)
	// 	{
	// 		string ans;
	// 		for(int l=0;l<n;l++)
	// 		{
	// 			if(mask&(1<<l))
	// 			{
	// 				ans+="B";
	// 			}
	// 			else{
	// 				ans+="D";
	// 			}
	// 		}
	// 		int cur=0;
	// 		for(int st=1;st<=n;st++)
	// 		{
	// 			for(int ot=1;ot<=n;ot++)
	// 				dist[ot]=1e11;
	// 			dist[st]=0;
	// 			priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	// 			pq.push({0,st});
	// 			while(pq.size())
	// 			{
	// 				auto it=pq.top();
	// 				pq.pop();
	// 				if(dist[it.second]==it.first)
	// 				{
	// 					for(auto [nxt,wei]:ma[it.second])
	// 					{
	// 						if(dist[nxt]>(wei+it.first))
	// 						{
	// 							dist[nxt]=wei+it.first;
	// 							pq.push({dist[nxt],nxt});
	// 						}
	// 					}
	// 				}
	// 			}
	// 			int D=1e11,B=1e11;
	// 			for(int ot=1;ot<=n;ot++)
	// 			{
	// 				if(ans[ot-1]=='B')
	// 				{
	// 					B=min(B,dist[ot]);
	// 				}
	// 				else
	// 				{
	// 					D=min(D,dist[ot]);
	// 				}
	// 			}
	// 			cur=max(cur,max(B,D));
	// 		}
	// 		if(cur<val)
	// 		{
	// 			val=cur;
	// 			an=ans;
	// 		}
	// 	}
	// 	cout<<val<<endl;
	// 	cout<<an<<endl;
	// }
	// else
	// {
		/*
			Lets think about DP
			mb the dp is like this dp[i][2] = in the subtree of i
		*/
		dfs(1);
		cout<<1<<endl;
		for(int j=1;j<=n;j++)
			cout<<ans1[j];
		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: 0
Wrong Answer
time: 0ms
memory: 15968kb

input:

3 3
1 2 3
2 3 1
1 3 2

output:

1
BDB

result:

wrong answer your claimed answer is 1, but the inconveniences of your plan is actually 3

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 347ms
memory: 63872kb

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:

1
BDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBD...

result:

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

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 24
Accepted

Test #31:

score: 24
Accepted
time: 287ms
memory: 44320kb

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
BBBBDDDBDBDBBDDDDBBDDBBDDDBBDBDDBDDDDBDDBBBBBDDDBDBDDDBBBBBDBDBBDBDDBDDBBBDDBBDBBBBDDBDBBDDDDBDBDDDDBDBBDBBDDDDBDDBBDBDBDDBBBDBDBBBBDBBBBBBDBBDBBDDDDBDBBBDBBBBBDDDBBDDBDDDBBDDBDBBBBBBBDBDDDBDBBBDDBDBBBDBDBBBBBDDBDBDBBBBDBBBBBBBDBBDBDBDDDBDBDDBBDBBDDBBBDBDDDBDDBBBBBDBBBBBBBDBBDBDBDBBDBBBBDBBDDBDDDB...

result:

ok inconveniences = 1

Test #32:

score: 0
Accepted
time: 359ms
memory: 46456kb

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
BBBDDDDDDBBDDDDDDBDDBBBDBBBDBBBDBDBDBDDDDBDDDBDDBDBBBBDBDBBBDBDDDBDDBDBBDBDBDDBBBBDBBDDBBDBDDBBBDBDBBBDBDBBDBBDBBBBDDBDBDBBDBBDBBDDDDDDBDBBDBDBDDDDBBDBDBDBDBDBDBDBDDDBBDBDBBDBBDDBBDDBDBDDDDDDDBBDDDDDBDDBBBDDDDDBBDBDBDBBDDBBDDDDBBBBDBBBBBBDDDBDDBDBBDBDBBBDDBDBDBBBDDBDBDDDBBBBBDDDDDBDDDDDDBBBBDBDBDB...

result:

ok inconveniences = 1

Test #33:

score: 0
Accepted
time: 74ms
memory: 25284kb

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
BBDDDBBDDBBDBBBDBBDBBBBDBBDBDDDDBDBBDDBBBDBDDDBBDBBDBBBBBDBBBDBDDBDDDBBDBBBBBDBBBDDBDBDBBBDBBDBDBDBDBBBBBDBDDBDBDBDBDDBDBBBBDDBBDBBBDDDDBDDBBBBDDBDDDBDDBBBDDBBDBDBDBBBBBBBDDDDBBBDDBBDDBDDDBBBBBDBDDDDBBBBDDBBDBDDDDDBBBBDDBDBDDBDDBBDDBBDBDDBDBBDBBDBDDBBDBBDDDBBBBBDDDBBDDBDBDDBBBBBBDDBDDDDBDDBDDDDDDD...

result:

ok inconveniences = 1

Test #34:

score: 0
Accepted
time: 220ms
memory: 38612kb

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
BBBBDBDDDDDDDDBBDBBBBBBDBDDDBDBBBBDDDDDBBBDBDDBBBDDDDDBBBBDBDDDBDBBDBBDDBDBBBDBDBDDDBBDBBDBDBDDBDBDDDDBDBDBBDDDDBDBBBBDBBBDBDBBDDDBDBDBDDBDDDDDDBBDDDDBBDBDDBBDDDDDDDBBBDBDDBDDBBDDDDBBDDDDDDDBBBBBDDBBDDBBDBBBBBDDBBBBDBDBBBDBBDBBBBBBBDDBBDBBDBBDBBDBBBBDBBDDBDBBDDBDDDDDBBDBDBBDBDBBDDBBDDDBBDDDBBDDDBD...

result:

ok inconveniences = 1

Test #35:

score: 0
Accepted
time: 321ms
memory: 49616kb

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
BDBDBDDDDBBDDBDBBBDBDBBBDBBDDDDBDDDBBDDBBDBBDBDBDBDBDBDDBBDBDBBDDBBDBBBDDDDDDBDBDDDBDBBBDDBDBDDDDDDDDBDBBDBDDBBDBBDBDBBDBDBDBBDBDDDBDBBBBBBBBBBBBBDDDDDDBBDBBBBBDBDBDBDDDBBBDBDBBBDBDDBBBBDBDBBBDBDDDBDDBDDDBDBDDBBDBBBBBBBDDDDBDDDDDBBBDDBBDBBDBBDDDDDDDDDBDBDDBDDBDBBDDDBBBBDBDBDDBBBDBDDBBBDDBBBDBDBBDD...

result:

ok inconveniences = 1

Test #36:

score: 0
Accepted
time: 358ms
memory: 45160kb

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
BBDDDDDBDDDDBDDBDBDBDDBBDDBBDBDDBBDDDDDDBBDDBBDDDDDBBDBDDBDBBDDBBBDBBBBBDBDBDBBDBBDBBDBBBDBDDBDBDDDDBBBDBBDBBDBDBBDDDDDBDBDBDBDBDBDDBDBDBDBBBDDDDDDDBDBBDBDBBDDBBDBBDDDDDDDBDDBBBBBBDDDDBBDDBBBDDDBBDBBDDBBBDDBBDBBDBDBDDDBDDBDBBDDDBDBBDDBBDBDBBDDBBDDDDDBDDBBBDDDDBBBDDDBBDDDDDBDDBDBBDBBDBDBBDDBDDDDDDB...

result:

ok inconveniences = 1

Test #37:

score: 0
Accepted
time: 358ms
memory: 43660kb

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
BBBBDBDBDDBDDDBDBDBBBDDDDBDDBDBBDBBBDDDDDBDDDDDBDBBBDDDDBDBBBDDBDDBDDDBDDBBBDBDDBDDBDDDBBDBDDBDDBBBBBBBBBBBBBBDBDDDBDDBBDDDBDBDBBBDDBDDBBBBBDDDBBBDBBDDDBBDBBDDBDBDDBDDDBBBBDBBBDBBBBDDDBDBDDBDDBDBDBDDDDDBBBBBBBBDBDBBBDBDBBBDDDDBDBDDDDDDDBBDBDDDDBDDDDBDDBBBBBBBBDBBDDDBBDBDBDDBDBDDDBBDBDBBBBDDBDBDBBB...

result:

ok inconveniences = 1

Test #38:

score: 0
Accepted
time: 369ms
memory: 44172kb

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
BBDBDDDBBDDDBBDBBBDBBDDDBDBBDDBDDBBDBBDBDDDBDDDDDBDDDDBDDDBDBDDDBDBDBBBBBDDDBBDBDDBDDBDDBBDBBBDBBBBDBDBDBDBBDBBDBBBDDBDBDBBDBBBBBDBBBBDDDDDDDBBBBBDDBBBBBBDBDDDBBBBBBDDBBBBBBBDDDDDBDBDBDDDDDDBBBDDBDDBBBBBBDBDBBBBBBBDDBDBBBBBBBDDDBBDDDDDBDBBBDBBBDBBDBBDBBDDBDBDDBBDBDBDBDDDBBDDDDBDBBBDBBBBBBDBBBBDBBD...

result:

ok inconveniences = 1

Test #39:

score: 0
Accepted
time: 364ms
memory: 43664kb

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
BDDDDBBDDDBBDBBDDBBDDDDBDBBBBDBDBBBBDBDBBBDBDBBDDBDDBDBBDBDBBDDBDDDDDBDBDBDBBBBDBDDDBBDDBBBDDBDBBDDDDDBDDBBDDBBDDDDBDDBDBBDBDDBDDBBDDBBBBBDBDBBDBBDBBBDDBDBBBBDDDBDDDDBDDDBBDBDDBBDDDDDBDBDDDDDBBDBDDBBDDDDBBDDDDDDDDDBBBBBBDBDDDBDBBDBDDBBBBBBBBDBBDBBBDDDBDDDBDDDBBBBBBBDBDBBBDDDBBDBDDDDBDBDDDDBDDDBDBD...

result:

ok inconveniences = 1

Test #40:

score: 0
Accepted
time: 352ms
memory: 44944kb

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
BDDBDDDDDDBDBDBBBDDDBBDBBBDDBDDBDDBDDBBBDDBDDBDBDBDDBBBBDDBBDDDDDBDDDDBDDDBDDBBBBDDBDBDDDDBBBBBBBBBDBBDBBDBBDBDBDBDBBDBBDBDDBBDDDBDDDDDBBDDBBDBDDDBBBBBBDBDDDBBDBDBBBBBDBDBDDBBDDDBBBBBBBDBBBBBBBBBDBBDDBDDBDDBBBBDDBDDBDBDDBDBBBBBBBBDBDDBBBDBDDDBDBDBBDBBDBBDBBDDBBBDDBBDBDBDDDBDDDBBBBDBDBBBDDDBBDDDDBB...

result:

ok inconveniences = 1

Subtask #5:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

Server Time: 2024-12-05 08:21:53 | OpenSource Project