QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#27439#2169. 'S No ProblemHakujitsu#AC ✓66ms13120kbC++1.4kb2022-04-09 16:27:252022-04-29 05:57:29

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-29 05:57:29]
  • 评测
  • 测评结果：AC
  • 用时：66ms
  • 内存：13120kb
查看
  • [2022-04-09 16:27:25]
  • 提交

answer

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define MAXN 100005
#define INF 1000000000
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int n;
vector<P> G[MAXN];
P maxi1[MAXN],maxi2[MAXN];
bool marked[MAXN];
int fa[MAXN];
pair<int,P> ans;
void dfs(int v,int p)
{
	maxi1[v]=P(0,v),maxi2[v]=P(-1,-1);
	for(auto e:G[v])
	{
		int to=e.F,cost=e.S;
		if(to==p) continue;
		dfs(to,v);
		if(marked[v]&&marked[to]) cost=-cost;
		if(maxi1[to].F+cost>maxi1[v].F)
		{
			maxi2[v]=maxi1[v];
			maxi1[v]=maxi1[to]; maxi1[v].F+=cost;
		}
		else if(maxi1[to].F+cost>maxi2[v].F)
		{
			maxi2[v]=maxi1[to]; maxi2[v].F+=cost;
		}
	}
	ans=max(ans,make_pair(maxi1[v].F,P(v,maxi1[v].S)));
	if(maxi2[v].F!=-1) ans=max(ans,make_pair(maxi1[v].F+maxi2[v].F,P(maxi2[v].S,maxi1[v].S)));
}
void dfs2(int v,int p)
{
	fa[v]=p;
	for(auto e:G[v])
	{
		int to=e.F,cost=e.S;
		if(to==p) continue;
		dfs2(to,v);
	}
}
int main()
{
	scanf("%d",&n);
	int sum=0;
	for(int i=0;i<n-1;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w); sum+=w;
		G[u].push_back(P(v,w)); G[v].push_back(P(u,w));
	}
	sum*=2;
	ans=make_pair(0,P(INF,INF));
	dfs(1,0);
	sum-=ans.F;
	dfs2(ans.S.F,0);
	int now=ans.S.S;
	while(now)
	{
		marked[now]=true;
		now=fa[now];
	}
	ans=make_pair(0,P(INF,INF));
	dfs(1,0);
	sum-=ans.F;
	printf("%d\n",sum);
	return 0;
}
Source code, Language: C++

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 7912kb

input:

5
1 2 1
1 3 2
1 4 3
1 5 4

output:

10

result:

ok single line: '10'

Test #2:

score: 0
Accepted
time: 4ms
memory: 8204kb

input:

6
6 2 1
4 6 1
3 1 1
1 5 1
1 6 10

output:

15

result:

ok single line: '15'

Test #3:

score: 0
Accepted
time: 3ms
memory: 6232kb

input:

6
1 3 1
3 2 1
3 4 10
5 4 1
4 6 1

output:

15

result:

ok single line: '15'

Test #4:

score: 0
Accepted
time: 3ms
memory: 6492kb

input:

6
1 3 1
2 3 1
3 5 1
4 5 1
5 6 1

output:

6

result:

ok single line: '6'

Test #5:

score: 0
Accepted
time: 2ms
memory: 6952kb

input:

6
1 2 5
3 2 3
2 4 1
4 5 2
4 6 4

output:

16

result:

ok single line: '16'

Test #6:

score: 0
Accepted
time: 4ms
memory: 6784kb

input:

6
1 6 8
2 6 2
3 6 3
4 6 5
5 6 1

output:

20

result:

ok single line: '20'

Test #7:

score: 0
Accepted
time: 1ms
memory: 7012kb

input:

7
6 4 60
4 2 463
6 7 165
6 3 81
6 1 30
4 5 214

output:

1103

result:

ok single line: '1103'

Test #8:

score: 0
Accepted
time: 4ms
memory: 6164kb

input:

7
1 3 463
1 5 214
7 2 165
7 4 81
7 1 60
7 6 30

output:

1103

result:

ok single line: '1103'

Test #9:

score: 0
Accepted
time: 4ms
memory: 6920kb

input:

8
8 7 10
1 3 1
3 2 1
6 5 2
5 4 1
3 7 4
7 5 3

output:

24

result:

ok single line: '24'

Test #10:

score: 0
Accepted
time: 5ms
memory: 7780kb

input:

8
1 2 1
2 3 1
3 4 10
3 5 10
2 6 1
6 7 10
6 8 10

output:

46

result:

ok single line: '46'

Test #11:

score: 0
Accepted
time: 4ms
memory: 6588kb

input:

8
6 7 1
7 8 1
8 1 10
8 3 10
7 5 1
5 2 10
5 4 10

output:

46

result:

ok single line: '46'

Test #12:

score: 0
Accepted
time: 4ms
memory: 6312kb

input:

10
8 9 6
10 9 6
9 1 2
1 5 11
5 6 1
5 7 1
1 3 10
3 2 3
3 4 3

output:

49

result:

ok single line: '49'

Test #13:

score: 0
Accepted
time: 1ms
memory: 6576kb

input:

10
1 3 1
2 3 1
3 5 1
4 5 1
5 6 1
5 9 1
7 9 1
8 9 1
9 10 1

output:

12

result:

ok single line: '12'

Test #14:

score: 0
Accepted
time: 4ms
memory: 6520kb

input:

10
1 2 1
1 3 1
1 4 1
3 5 1
4 6 1
6 7 1
3 8 1
7 9 1
8 10 1

output:

10

result:

ok single line: '10'

Test #15:

score: 0
Accepted
time: 1ms
memory: 7904kb

input:

10
1 10 1
1 6 1
2 10 1
3 5 1
3 7 1
3 10 1
4 5 1
4 9 1
8 9 1

output:

10

result:

ok single line: '10'

Test #16:

score: 0
Accepted
time: 5ms
memory: 6816kb

input:

10
1 2 1
1 3 1
2 4 2
3 5 1
2 6 1
2 7 1
2 8 2
2 9 2
2 10 2

output:

17

result:

ok single line: '17'

Test #17:

score: 0
Accepted
time: 37ms
memory: 13120kb

input:

100000
1 2 1
1 20001 1
1 40001 1
1 60001 1
1 80001 1
2 3 1
20001 20002 1
40001 40002 1
60001 60002 1
80001 80002 1
3 4 1
20002 20003 1
40002 40003 1
60002 60003 1
80002 80003 1
4 5 1
20003 20004 1
40003 40004 1
60003 60004 1
80003 80004 1
5 6 1
20004 20005 1
40004 40005 1
60004 60005 1
80004 80005 1...

output:

119998

result:

ok single line: '119998'

Test #18:

score: 0
Accepted
time: 0ms
memory: 7000kb

input:

11
11 4 1
10 4 10
9 3 1
8 2 6
7 4 20
6 3 5
5 2 7
4 3 2
3 2 3
2 1 10

output:

82

result:

ok single line: '82'

Test #19:

score: 0
Accepted
time: 5ms
memory: 6708kb

input:

11
10 4 7
7 11 20
7 8 2
6 8 1
8 1 5
3 7 1
8 10 3
2 7 10
5 10 6
10 9 10

output:

82

result:

ok single line: '82'

Test #20:

score: 0
Accepted
time: 5ms
memory: 6968kb

input:

11
1 2 2
2 3 1
1 4 3
4 5 4
1 6 5
6 7 6
1 8 7
8 9 8
1 10 9
10 11 10

output:

58

result:

ok single line: '58'

Test #21:

score: 0
Accepted
time: 5ms
memory: 6612kb

input:

11
4 1 2
4 7 3
7 8 4
9 6 8
4 5 5
5 3 6
4 9 7
1 11 1
4 2 9
2 10 10

output:

58

result:

ok single line: '58'

Test #22:

score: 0
Accepted
time: 3ms
memory: 7532kb

input:

12
9 2 2
2 10 10
2 12 11
1 12 3
12 8 5
12 11 7
12 7 1
4 7 8
3 7 4
7 6 9
7 5 6

output:

87

result:

ok single line: '87'

Test #23:

score: 0
Accepted
time: 2ms
memory: 7824kb

input:

12
8 2 10
7 12 10
1 7 10
4 2 10
2 1 1
9 6 3
5 9 3
1 9 1
10 9 3
9 11 3
3 9 3

output:

70

result:

ok single line: '70'

Test #24:

score: 0
Accepted
time: 2ms
memory: 7472kb

input:

12
7 3 3
10 3 8
3 2 4
11 2 4
2 12 6
2 1 3
3 4 6
3 6 2
4 8 5
4 5 1
4 9 7

output:

64

result:

ok single line: '64'

Test #25:

score: 0
Accepted
time: 5ms
memory: 7060kb

input:

14
9 5 1
11 14 1
13 8 2
6 8 2
3 13 2
12 2 1
8 12 1
10 5 1
1 8 1
5 8 1
7 12 1
14 8 1
4 6 2

output:

22

result:

ok single line: '22'

Test #26:

score: 0
Accepted
time: 2ms
memory: 7192kb

input:

15
1 3 1
2 3 1
3 5 1
4 5 1
5 6 1
5 9 1
7 9 1
8 9 1
9 10 1
9 13 1
11 13 1
12 13 1
13 14 1
13 15 1

output:

21

result:

ok single line: '21'

Test #27:

score: 0
Accepted
time: 1ms
memory: 8140kb

input:

15
1 6 1
2 9 1
3 2 3
5 4 1
6 5 1
7 2 3
8 2 3
9 1 1
10 11 1
12 14 1
13 14 1
15 2 3
2 13 1
10 12 1

output:

28

result:

ok single line: '28'

Test #28:

score: 0
Accepted
time: 7ms
memory: 6568kb

input:

16
1 3 1
2 3 1
3 10 1
10 5 1
5 4 1
5 6 1
10 9 1
7 9 1
8 9 1
16 10 1
14 16 1
16 15 1
10 11 1
11 13 1
12 11 1

output:

22

result:

ok single line: '22'

Test #29:

score: 0
Accepted
time: 2ms
memory: 6612kb

input:

20
1 2 154
1 3 125
3 4 242
1 5 415
5 6 250
2 7 245
1 8 477
1 9 284
2 10 220
8 11 437
4 12 186
7 13 73
3 14 22
2 15 365
1 16 138
15 17 132
11 18 79
3 19 285
4 20 61

output:

5518

result:

ok single line: '5518'

Test #30:

score: 0
Accepted
time: 2ms
memory: 7304kb

input:

25
1 2 147
2 3 259
2 4 270
1 5 435
4 6 421
4 7 236
5 8 169
7 9 448
2 10 472
10 11 496
10 12 131
1 13 148
1 14 187
3 15 214
11 16 128
10 17 378
5 18 156
5 19 62
8 20 480
14 21 176
6 22 412
19 23 389
3 24 244
21 25 318

output:

9588

result:

ok single line: '9588'

Test #31:

score: 0
Accepted
time: 5ms
memory: 7180kb

input:

30
1 2 428
2 3 240
3 4 229
3 5 372
3 6 49
4 7 116
1 8 271
7 9 311
1 10 47
6 11 59
6 12 405
1 13 161
3 14 414
8 15 467
1 16 480
1 17 274
12 18 251
6 19 169
19 20 480
15 21 378
5 22 484
12 23 486
20 24 224
20 25 186
7 26 401
9 27 327
24 28 401
16 29 79
16 30 429

output:

12290

result:

ok single line: '12290'

Test #32:

score: 0
Accepted
time: 0ms
memory: 6144kb

input:

100
1 2 1
1 3 1
2 4 1
2 5 1
2 6 1
6 7 1
7 8 1
4 9 1
9 10 1
9 11 1
11 12 1
5 13 1
2 14 1
14 15 1
1 16 1
3 17 1
4 18 1
13 19 1
4 20 1
14 21 1
19 22 1
5 23 1
14 24 1
17 25 1
4 26 1
12 27 1
16 28 1
9 29 1
6 30 1
22 31 1
19 32 1
24 33 1
16 34 1
15 35 1
2 36 1
23 37 1
25 38 1
3 39 1
37 40 1
32 41 1
28 42 ...

output:

173

result:

ok single line: '173'

Test #33:

score: 0
Accepted
time: 4ms
memory: 6224kb

input:

500
1 2 1
2 3 1
3 4 1
1 5 1
3 6 1
3 7 1
5 8 1
8 9 1
4 10 1
3 11 1
5 12 1
1 13 1
2 14 1
10 15 1
14 16 1
7 17 1
5 18 1
4 19 1
19 20 1
18 21 1
19 22 1
7 23 1
18 24 1
19 25 1
24 26 1
10 27 1
18 28 1
8 29 1
22 30 1
5 31 1
2 32 1
7 33 1
19 34 1
33 35 1
9 36 1
5 37 1
17 38 1
35 39 1
24 40 1
27 41 1
27 42 1...

output:

960

result:

ok single line: '960'

Test #34:

score: 0
Accepted
time: 2ms
memory: 6544kb

input:

1000
1 2 1
1 3 1
3 4 1
4 5 1
2 6 1
6 7 1
5 8 1
4 9 1
2 10 1
7 11 1
10 12 1
10 13 1
11 14 1
11 15 1
9 16 1
16 17 1
3 18 1
1 19 1
12 20 1
6 21 1
8 22 1
20 23 1
18 24 1
9 25 1
14 26 1
24 27 1
1 28 1
17 29 1
6 30 1
5 31 1
9 32 1
17 33 1
10 34 1
23 35 1
35 36 1
1 37 1
24 38 1
38 39 1
9 40 1
25 41 1
18 42...

output:

1951

result:

ok single line: '1951'

Test #35:

score: 0
Accepted
time: 5ms
memory: 7164kb

input:

1000
1 2 9
2 3 9
2 4 4
2 5 7
2 6 3
2 7 10
7 8 3
2 9 3
2 10 4
8 11 9
10 12 2
6 13 1
5 14 3
11 15 4
15 16 1
5 17 9
6 18 9
18 19 8
13 20 5
9 21 7
12 22 3
12 23 5
23 24 10
16 25 4
24 26 9
15 27 6
6 28 4
24 29 6
28 30 3
28 31 8
9 32 2
24 33 5
22 34 5
19 35 1
29 36 5
31 37 1
31 38 10
25 39 3
33 40 2
22 41...

output:

10691

result:

ok single line: '10691'

Test #36:

score: 0
Accepted
time: 4ms
memory: 7236kb

input:

1000
1 2 9
2 3 6
1 4 3
1 5 1
5 6 1
1 7 3
2 8 5
6 9 5
5 10 8
8 11 9
5 12 9
3 13 2
6 14 5
8 15 3
13 16 6
1 17 1
10 18 8
5 19 8
15 20 5
9 21 9
2 22 2
5 23 7
7 24 4
9 25 3
6 26 7
11 27 5
18 28 1
18 29 6
14 30 5
5 31 5
18 32 9
10 33 1
32 34 4
15 35 10
6 36 3
29 37 5
5 38 9
25 39 4
37 40 7
9 41 6
31 42 10...

output:

10698

result:

ok single line: '10698'

Test #37:

score: 0
Accepted
time: 50ms
memory: 11856kb

input:

100000
1 2 6
1 3 3
1 4 3
3 5 1
3 6 6
5 7 4
4 8 2
4 9 1
7 10 8
6 11 7
4 12 3
12 13 10
7 14 4
8 15 8
10 16 1
3 17 8
5 18 1
16 19 4
13 20 1
4 21 10
20 22 7
12 23 10
6 24 3
22 25 5
21 26 2
15 27 7
10 28 4
8 29 6
26 30 9
14 31 10
15 32 5
19 33 6
6 34 2
18 35 2
14 36 5
29 37 7
10 38 2
37 39 6
32 40 3
17 4...

output:

1096451

result:

ok single line: '1096451'

Test #38:

score: 0
Accepted
time: 66ms
memory: 11844kb

input:

100000
1 2 322
1 3 195
2 4 186
1 5 249
4 6 431
1 7 445
7 8 73
7 9 71
1 10 319
9 11 183
7 12 434
7 13 186
12 14 341
2 15 472
14 16 2
14 17 71
15 18 117
12 19 69
12 20 29
10 21 138
19 22 100
22 23 30
16 24 224
14 25 283
22 26 310
13 27 215
10 28 278
2 29 201
21 30 234
9 31 34
23 32 349
26 33 194
2 34 ...

output:

50027510

result:

ok single line: '50027510'

Test #39:

score: 0
Accepted
time: 57ms
memory: 11820kb

input:

100000
1 2 146
2 3 135
2 4 303
3 5 300
1 6 227
5 7 279
7 8 173
2 9 340
6 10 367
7 11 363
1 12 104
12 13 134
13 14 310
5 15 374
3 16 231
5 17 60
11 18 395
14 19 350
11 20 448
6 21 287
21 22 111
9 23 40
15 24 223
2 25 158
24 26 272
15 27 470
2 28 397
11 29 357
11 30 296
19 31 267
4 32 211
19 33 272
17...

output:

50072806

result:

ok single line: '50072806'

Test #40:

score: 0
Accepted
time: 65ms
memory: 11860kb

input:

100000
1 2 378
1 3 164
2 4 255
1 5 142
1 6 152
4 7 276
4 8 157
7 9 209
1 10 407
10 11 481
8 12 150
7 13 67
8 14 316
2 15 297
12 16 137
8 17 436
7 18 151
5 19 215
13 20 256
20 21 392
12 22 266
11 23 480
8 24 491
2 25 490
25 26 190
8 27 210
21 28 400
14 29 77
25 30 12
22 31 129
26 32 332
26 33 2
18 34...

output:

50132921

result:

ok single line: '50132921'

Test #41:

score: 0
Accepted
time: 56ms
memory: 11872kb

input:

100000
1 2 280
1 3 358
2 4 95
4 5 225
2 6 329
6 7 338
6 8 431
5 9 480
3 10 418
3 11 357
1 12 433
1 13 248
13 14 107
13 15 370
11 16 94
4 17 119
16 18 265
7 19 62
8 20 261
18 21 225
5 22 311
1 23 353
1 24 254
14 25 379
11 26 152
9 27 490
15 28 131
1 29 126
4 30 298
20 31 432
15 32 397
10 33 173
4 34 ...

output:

50101696

result:

ok single line: '50101696'

Test #42:

score: 0
Accepted
time: 0ms
memory: 7208kb

input:

1000
970 113 1
569 319 1
715 682 279
804 299 210
615 353 1
733 464 1
306 245 1
180 779 281
841 284 1
1 402 1
21 229 1
128 323 1
76 55 1
57 467 1
943 967 1
572 158 1
690 927 1
15 655 1
430 146 1
374 31 1
825 399 1
368 669 1
524 375 1
616 91 1
121 20 1
604 759 1
186 730 1
697 816 1
837 84 1
73 461 1
5...

output:

23594

result:

ok single line: '23594'

Test #43:

score: 0
Accepted
time: 4ms
memory: 6296kb

input:

1000
343 861 1
967 872 1
364 889 1
290 807 1
390 832 1
302 173 1
590 252 1
238 232 1
742 432 1
180 291 1
358 997 1
73 728 1
971 526 1
61 6 1
433 486 1
96 325 1
124 790 1
605 360 1
923 41 1
229 618 1
263 721 1
669 784 1
774 393 1
659 481 1
514 132 259
376 909 1
841 537 1
538 133 1
385 453 1
651 437 1...

output:

20965

result:

ok single line: '20965'

Test #44:

score: 0
Accepted
time: 5ms
memory: 7020kb

input:

1000
330 988 1
586 881 1
820 772 1
540 624 1
592 367 1
467 888 1
502 518 1
481 676 1
778 549 1
582 590 1
313 554 1
846 406 1
844 472 1
831 807 1
321 480 1
902 67 1
957 649 1
588 373 1
591 33 1
947 829 1
866 421 1
628 71 1
84 6 1
780 185 1
301 322 1
283 715 1
151 930 1
28 545 1
107 333 1
744 112 1
36...

output:

21791

result:

ok single line: '21791'

Test #45:

score: 0
Accepted
time: 2ms
memory: 8044kb

input:

1000
478 306 1
797 508 1
864 719 1
413 654 1
842 167 1
289 709 1
389 91 1
762 372 1
634 461 1
766 462 1
220 240 1
352 422 1
253 813 1
264 43 1
502 608 1
538 450 1
480 735 1
463 223 1
486 313 1
648 307 1
31 298 1
959 173 1
839 861 1
588 184 1
260 999 1
224 295 1
955 742 1
790 898 1
535 552 1
287 691 ...

output:

22674

result:

ok single line: '22674'

Test #46:

score: 0
Accepted
time: 2ms
memory: 7356kb

input:

1000
99 52 1
775 540 1
651 833 338
3 704 489
930 609 1
824 276 1
678 111 1
52 962 1
718 680 1
829 649 1
450 432 1
412 680 1
222 852 1
214 96 1
297 647 1
809 370 1
568 742 1
416 574 1
594 84 491
244 287 1
998 490 1
802 598 1
388 96 1
221 760 1
949 553 1
964 886 1
543 174 1
757 402 1
441 243 1
107 338...

output:

22176

result:

ok single line: '22176'

Test #47:

score: 0
Accepted
time: 2ms
memory: 7472kb

input:

1000
738 130 1
966 995 1
285 477 1
857 298 1
768 323 1
799 828 1
602 974 1
389 113 1
576 721 1
539 405 1
396 64 1
548 749 1
234 741 1
843 314 1
577 816 1
545 422 1
392 229 1
927 724 1
587 936 1
598 173 1
59 773 1
881 40 302
94 157 1
847 870 1
134 595 1
377 8 1
97 144 1
824 103 1
709 240 1
953 155 1
...

output:

22397

result:

ok single line: '22397'

Test #48:

score: 0
Accepted
time: 4ms
memory: 6572kb

input:

1000
259 670 1
215 261 1
522 62 1
69 711 1
609 466 1
540 756 1
553 661 1
406 509 1
531 677 1
481 166 1
187 755 1
316 35 1
729 863 1
916 290 1
193 171 1
305 926 1
906 605 483
395 397 1
117 560 1
946 707 1
753 931 476
28 985 1
341 640 1
668 969 1
983 181 1
940 450 1
960 336 1
622 812 1
725 77 1
295 86...

output:

21391

result:

ok single line: '21391'

Test #49:

score: 0
Accepted
time: 5ms
memory: 7596kb

input:

1000
488 525 1
458 238 1
999 495 1
321 709 1
635 741 1
966 886 1
667 666 1
815 146 1
996 227 1
380 442 1
196 2 1
463 60 1
745 590 1
659 47 1
357 915 1
924 316 1
940 727 1
705 142 1
652 356 1
462 631 1
518 219 1
70 102 1
325 182 1
831 653 1
231 914 1
122 825 1
301 854 1
546 572 1
985 321 1
311 273 1
...

output:

23159

result:

ok single line: '23159'

Test #50:

score: 0
Accepted
time: 4ms
memory: 8072kb

input:

1000
6 849 1
954 404 1
897 570 1
412 229 1
413 873 94
968 339 1
264 484 1
274 857 1
443 51 1
670 487 1
95 516 1
216 544 1
625 146 1
806 228 1
655 125 1
731 796 1
353 712 1
540 405 1
775 133 1
96 442 1
298 396 1
68 668 1
162 676 1
13 749 1
43 743 1
251 547 1
461 911 1
883 135 1
449 274 1
617 49 1
718...

output:

17260

result:

ok single line: '17260'

Test #51:

score: 0
Accepted
time: 2ms
memory: 7780kb

input:

1000
241 93 1
979 567 1
169 610 1
242 913 1
746 555 1
201 240 1
70 286 1
718 268 1
484 802 1
754 364 1
505 139 1
228 33 1
959 430 1
434 456 1
691 885 1
696 781 1
946 39 1
991 183 1
966 181 1
951 713 1
803 27 1
371 147 1
305 102 1
529 724 1
888 193 1
314 229 1
323 431 1
515 223 1
728 123 1
150 743 1
...

output:

24880

result:

ok single line: '24880'

Test #52:

score: 0
Accepted
time: 4ms
memory: 6348kb

input:

1000
565 515 1
672 576 1
926 488 142
200 175 1
588 650 1
779 27 1
267 845 1
309 788 1
680 657 1
85 467 1
413 809 1
146 15 1
539 784 1
509 496 1
844 863 1
248 643 1
213 896 1
143 626 1
783 322 1
849 776 1
39 262 1
379 212 1
774 415 1
638 823 1
932 811 1
823 476 1
766 459 1
149 216 1
14 574 1
996 855 ...

output:

20705

result:

ok single line: '20705'

Test #53:

score: 0
Accepted
time: 5ms
memory: 6928kb

input:

1000
159 193 1
401 230 1
696 220 1
464 977 1
356 198 1
253 875 1
641 444 1
82 693 1
629 882 191
767 943 1
421 203 1
360 364 1
161 17 1
814 165 1
802 150 1
816 136 1
757 836 1
863 459 1
212 590 376
648 468 1
84 811 1
289 73 1
948 593 1
62 940 1
407 721 1
784 397 1
938 521 33
68 23 1
214 374 1
635 373...

output:

44159

result:

ok single line: '44159'

Test #54:

score: 0
Accepted
time: 2ms
memory: 7384kb

input:

1000
621 894 1
496 503 1
84 507 1
814 636 1
538 248 1
718 15 1
494 984 1
41 218 1
405 278 1
599 47 1
904 393 1
84 534 1
382 774 1
210 569 1
407 987 1
43 315 1
609 864 1
750 955 1
186 347 1
94 554 46
616 760 1
818 595 1
249 972 1
967 600 1
692 156 1
367 952 1
872 183 1
286 630 1
802 957 1
107 834 1
3...

output:

19557

result:

ok single line: '19557'

Test #55:

score: 0
Accepted
time: 5ms
memory: 7768kb

input:

1000
909 598 1
318 790 1
641 276 1
130 773 1
945 502 1
32 981 1
441 515 1
823 37 1
850 390 1
612 119 1
292 527 1
24 716 1
681 427 94
559 448 1
661 811 1
957 901 1
980 58 380
526 374 1
60 286 245
835 797 1
954 164 1
702 801 1
210 342 1
193 1000 1
926 708 1
181 587 1
824 156 64
936 153 1
302 239 1
576...

output:

21173

result:

ok single line: '21173'

Test #56:

score: 0
Accepted
time: 2ms
memory: 8008kb

input:

1000
427 917 1
735 780 1
637 565 1
301 305 1
501 459 1
319 469 1
179 551 1
15 574 1
778 723 1
892 863 1
257 986 1
346 282 1
878 719 1
430 86 1
442 40 1
70 78 1
91 363 1
266 801 1
426 648 1
272 882 1
862 365 1
555 732 1
983 511 1
828 730 1
768 966 1
703 855 1
660 512 1
355 202 1
90 728 1
181 893 1
84...

output:

25619

result:

ok single line: '25619'

Test #57:

score: 0
Accepted
time: 5ms
memory: 7500kb

input:

1000
807 431 1
879 763 1
297 440 60
529 525 1
298 759 1
403 453 1
336 109 1
901 256 1
902 442 1
526 921 1
310 108 1
121 219 1
351 623 1
580 423 1
321 704 1
85 62 1
632 163 1
273 271 492
757 323 1
408 496 1
828 933 1
946 665 1
67 486 1
249 841 1
859 145 1
878 970 1
947 849 1
118 680 406
534 770 1
818...

output:

19627

result:

ok single line: '19627'

Test #58:

score: 0
Accepted
time: 0ms
memory: 6404kb

input:

1000
965 763 1
965 960 3
965 205 3
965 562 5
334 965 4
808 965 3
400 965 5
965 420 4
965 620 4
578 965 1
153 965 1
965 914 5
965 915 1
640 965 2
115 965 3
271 965 3
425 965 1
930 965 3
965 31 5
965 243 4
471 965 2
348 965 1
965 149 5
965 417 3
965 74 2
275 965 5
965 542 1
965 661 1
965 95 300
965 18...

output:

10696

result:

ok single line: '10696'

Test #59:

score: 0
Accepted
time: 2ms
memory: 6856kb

input:

1000
486 440 3
843 440 2
440 203 4
213 440 4
440 412 4
149 440 2
657 440 2
41 440 3
855 440 1
683 440 3
440 116 5
440 537 5
808 440 5
975 440 3
440 88 5
440 817 3
675 440 1
837 440 4
645 440 4
440 436 5
993 440 1
318 440 1
440 91 1
269 440 4
440 796 2
440 472 3
416 440 3
137 440 2
440 159 4
440 229 ...

output:

10790

result:

ok single line: '10790'

Test #60:

score: 0
Accepted
time: 4ms
memory: 6400kb

input:

1000
647 232 1
362 647 2
723 647 1
647 714 3
647 994 4
185 647 2
294 647 4
647 480 3
647 464 4
536 647 2
647 818 1
512 647 5
647 974 3
647 442 3
88 647 5
647 584 1
176 647 3
726 647 2
647 728 2
647 613 5
983 647 1
296 647 2
503 647 5
647 135 5
647 233 1
647 126 5
96 647 1
647 349 5
471 647 5
647 684...

output:

10898

result:

ok single line: '10898'

Test #61:

score: 0
Accepted
time: 5ms
memory: 7732kb

input:

1000
921 861 5
861 262 5
220 861 5
861 553 3
861 634 4
621 861 3
954 861 4
861 71 5
788 861 3
974 861 5
861 261 1
861 358 4
861 396 3
861 340 1
861 415 3
868 861 4
93 861 4
591 861 1
579 861 3
424 861 4
861 537 1
121 861 2
269 861 4
625 861 3
861 753 1
861 430 4
861 15 3
732 861 2
83 861 4
131 861 3...

output:

11050

result:

ok single line: '11050'

Test #62:

score: 0
Accepted
time: 5ms
memory: 7616kb

input:

1000
538 748 1
823 68 1
289 379 1
690 795 1
585 650 1
374 333 1
234 863 1
196 825 1
665 645 1
420 469 1
493 926 1
670 10 1
951 201 1
299 235 1
368 918 1
68 975 1
941 814 1
149 562 1
945 535 1
622 431 1
805 575 1
466 99 1
567 286 1
313 984 1
989 442 1
78 544 1
268 132 1
625 627 1
937 320 1
697 204 1
...

output:

25762

result:

ok single line: '25762'

Test #63:

score: 0
Accepted
time: 4ms
memory: 6640kb

input:

1000
399 7 1
897 195 1
534 415 1
329 409 1
52 895 1
387 144 1
316 287 1
721 754 1
90 174 1
993 911 1
877 303 1
95 869 1
908 367 343
774 781 1
158 834 1
282 367 404
641 266 1
309 445 488
377 976 1
179 425 1
185 11 1
157 660 1
977 495 1
23 424 1
665 546 1
442 105 1
859 438 1
592 682 1
930 493 1
927 71...

output:

22906

result:

ok single line: '22906'
English 繁體中文 简体中文

Server Time: 2024-11-29 18:48:22 | OpenSource Project