QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#561402#5313. Please Save PigelandhhdhhAC ✓1096ms138880kbC++233.8kb2024-09-12 22:13:082024-09-12 22:13:09

Judging History

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

  • [2024-09-12 22:13:09]
  • 评测
  • 测评结果:AC
  • 用时:1096ms
  • 内存:138880kb
  • [2024-09-12 22:13:08]
  • 提交

answer

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

#define endl '\n'
#define rep(i, a, b) for(LL i = (a); i <= (b); i++)
#define per(i, a, b) for(LL i = (a); i >= (b); i--)
#define rept(i, a, ne) for(LL i = (a); ~i ; i=ne[i])
#define debug(x) cout<<#x<<": "<<x<<endl
#define fi first
#define sec second
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef long long LL;
typedef long double  LD;
typedef unsigned long long ULL;
typedef vector<LL> VI;
typedef pair<LL,LL>PII;

const LL N=1e6+10,M=2*N;

#define lc u<<1
#define rc u<<1|1

LL rk[N];
LL b[N];

struct Tree
{ //线段树
	LL l,r;
	LL sum,d;
}tr[N*4];

void pushup(LL u)
{ //上传
	tr[u].sum=tr[lc].sum+tr[rc].sum;
	tr[u].d=__gcd(tr[lc].d,tr[rc].d);
}

void init(LL u,LL l,LL r)
{ //建树
	tr[u]={l,r,b[l],b[l]};
	if(l==r) return;
	LL m=l+r>>1;
	init(lc,l,m);
	init(rc,m+1,r);
	pushup(u);
}

void change(LL u,LL x,LL k)
{ //点修
	if(x==tr[u].l&&tr[u].r==x)
	{
		tr[u].sum+=k;
		tr[u].d+=k;
		return;
	}
	LL m=tr[u].l+tr[u].r>>1;
	if(x<=m) change(lc,x,k);
	if(x>m) change(rc,x,k);
	pushup(u);
}
LL queryG(LL u,LL l,LL r)
{ //区查
	if(l<=tr[u].l && tr[u].r<=r) return tr[u].d;
	LL m=tr[u].l+tr[u].r>>1;
	
	if(l<=m&&r>m)
		return __gcd(queryG(lc,l,r),queryG(rc,l,r));
	else if(l<=m)
        return queryG(lc,l,r);
	else 
	    return queryG(rc,l,r);
}
LL querys(LL u,LL l,LL r)
{ //区查
	if(l<=tr[u].l && tr[u].r<=r) return tr[u].sum;
	LL m=tr[u].l+tr[u].r>>1;
	LL sum=0;
	if(l<=m) sum+=querys(lc,l,r);
	if(r>m) sum+=querys(rc,l,r);
	return sum;
}
LL h[N],ne[M],w[M],e[M],idx;
LL dfn[N],num;
LL sz[N];
LL l[N],r[N];
LL d[N];
bool bo[N];

void add(LL x,LL y,LL z)
{
    w[idx]=z,e[idx]=y,ne[idx]=h[x],h[x]=idx++;
}
void dfs(LL x,LL fa)
{
    if(bo[x])
    {
        dfn[x]=++num;
        sz[x]=1;
        rk[num]=x;
        l[x]=r[x]=num;
    }
    
    
    rept(i,h[x],ne)
    {
        LL y=e[i];
        if(y==fa)continue;
        d[y]=w[i]+d[x];
        dfs(y,x);
        sz[x]+=sz[y];
        l[x]=min(l[x],l[y]);
        r[x]=max(r[x],r[y]);
    }
    

}
LL mi;
LL getgcd(LL x,LL y)
{
	LL sum=querys(1,1,x);
    LL d=0;
    if(x<y)
        d=queryG(1,x+1,y);
    return abs(__gcd(sum,d));//因为如果查一个点会直接返回d(有可能是负数)
}
void dfs2(LL x,LL fa,LL sum)
{
    mi=min(sum/getgcd(1,num),mi);
 
    rept(i,h[x],ne)
    {
        LL y=e[i];
        if(y==fa)continue;
        
        LL psum=sum+(num-2*sz[y])*w[i];
        //修改
        if(l[y]>r[y])
            change(1,1,w[i]);
        else
        {
            change(1,1,w[i]);
            change(1,l[y],-w[i]*2);
    
            if(r[y]<num)
            change(1,r[y]+1,w[i]*2);
        }
        dfs2(y,x,psum);
        //还原
        if(l[y]>r[y])
            change(1,1,-w[i]);
        else
        {
            change(1,1,-w[i]);
            change(1,l[y],w[i]*2);
            if(r[y]<num)
            change(1,r[y]+1,-w[i]*2);
        }
    }
}
void slove()
{
    memset(h,-1,sizeof h);
    memset(l,0x3f,sizeof l);
    mi=LLONG_MAX;
    LL n,m;
    cin>>n>>m;
    rep(i,1,m)
    {
        LL x;
        cin>>x;
        bo[x]=1;

    }
    
    rep(i,1,n-1)
    {
        LL x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    if(m==1)
    {
        cout<<0<<endl;
        return;
    }
    dfs(1,0);
    LL sum=0;
    
    rep(i,1,num)
    {
        b[i]=d[rk[i]]-d[rk[i-1]];
        sum+=d[rk[i]];
    }
  
    init(1,1,num);


    dfs2(1,0,sum);
    cout<<mi*2<<endl;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
//	cout << fixed << setprecision(9);
    LL t=1;
//	cin>>t;
    while(t--)
    {
        slove();
    }


    return 0;
}
//#pragma GCC optimize(2)

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 34292kb

input:

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

output:

8

result:

ok 1 number(s): "8"

Test #2:

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

input:

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

output:

24

result:

ok 1 number(s): "24"

Test #3:

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

input:

1 1
1

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 13ms
memory: 33720kb

input:

100000 1
79187
72704 72659 15
32741 43496 10
21580 97447 17
55758 36700 21
32116 3643 14
60460 58764 12
75894 50624 7
58295 49393 22
43733 17210 1
58093 68769 15
1086 58916 17
25632 37710 11
49555 92976 8
32547 27060 18
84896 12811 1
3196 1242 16
18870 78236 14
2414 7945 12
48745 15399 1
17648 83791...

output:

0

result:

ok 1 number(s): "0"

Test #5:

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

input:

100 10
3 27 33 45 48 72 76 91 92 100
66 98 4
70 17 2
28 59 4
26 25 3
77 92 1
40 61 2
11 27 2
85 35 1
57 26 1
68 99 4
50 84 1
20 82 3
31 39 1
71 7 4
54 55 4
60 26 4
56 61 2
15 66 3
95 53 2
8 60 4
21 82 1
18 81 2
29 73 3
94 4 1
10 4 4
86 43 1
62 41 1
45 57 1
25 66 3
69 89 2
14 53 3
27 92 1
42 98 4
13 ...

output:

200

result:

ok 1 number(s): "200"

Test #6:

score: 0
Accepted
time: 6ms
memory: 34492kb

input:

100 90
75 17 78 84 52 69 54 24 74 35 58 51 72 7 21 70 93 15 60 87 13 40 23 92 99 53 27 22 91 46 56 86 61 19 44 98 50 28 14 12 55 64 30 80 95 38 18 43 31 89 20 16 8 65 63 79 59 34 97 25 2 11 67 71 29 9 37 76 77 26 39 68 32 62 90 10 85 49 42 45 96 83 94 3 6 100 81 57 88 47
67 65 1
43 78 4
98 71 3
71 2...

output:

1798

result:

ok 1 number(s): "1798"

Test #7:

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

input:

1000 10
111 240 479 530 572 583 644 652 753 869
121 923 2
886 685 4
446 284 4
352 250 1
540 485 2
72 154 4
522 693 3
664 917 4
792 941 3
132 832 4
709 186 3
509 114 2
824 978 2
216 265 2
138 570 1
498 959 4
434 222 1
803 693 1
253 677 4
172 463 3
383 978 2
718 959 3
369 421 4
568 454 4
256 938 1
6 1...

output:

226

result:

ok 1 number(s): "226"

Test #8:

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

input:

1000 957
233 514 228 739 827 85 840 175 766 807 19 276 549 611 145 511 895 121 116 525 280 431 810 629 990 509 542 324 241 801 849 506 178 176 49 528 221 742 444 513 111 505 442 794 107 392 291 674 298 803 198 927 738 590 706 804 860 512 421 618 697 516 335 420 418 288 544 694 330 776 104 510 621 47...

output:

32602

result:

ok 1 number(s): "32602"

Test #9:

score: 0
Accepted
time: 341ms
memory: 69844kb

input:

500000 4
182462 188845 259396 281751
456733 79213 9204078
395954 45205 3919968
454058 310013 734433
433648 435834 3887333
448797 138275 9946222
385528 63721 3037094
44276 184047 1799127
169565 81666 3752583
459111 229807 5534913
374868 374333 8627923
476055 408523 2692999
445258 424229 3038119
92885...

output:

193870600

result:

ok 1 number(s): "193870600"

Test #10:

score: 0
Accepted
time: 601ms
memory: 91912kb

input:

500000 150000
1 4 6 12 19 20 21 24 30 34 35 37 39 40 41 45 47 48 49 51 60 65 71 72 75 80 83 84 90 93 94 96 97 99 105 113 115 125 128 132 135 136 138 139 142 145 146 150 152 159 164 167 179 180 186 188 189 190 195 200 204 205 208 210 211 212 214 217 223 226 230 233 238 243 247 260 263 264 268 269 271...

output:

8719582

result:

ok 1 number(s): "8719582"

Test #11:

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

input:

1000 10
334 271 592 707 890 566 590 450 169 129
784 868 7940645
969 691 6692155
864 76 6691895
853 343 2376735
12 897 7467840
783 560 3342995
908 372 952130
5 843 3055195
531 64 7912240
313 701 2196620
246 52 9831250
808 788 6735060
414 340 168805
278 276 6271820
97 247 2379595
490 459 701440
422 45...

output:

15519516

result:

ok 1 number(s): "15519516"

Test #12:

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

input:

1000 10
935 536 379 686 787 66 829 374 369 957
913 887 7565610
118 846 8734750
109 698 7065147
156 813 2228752
769 869 9612951
887 99 4384470
253 494 6908549
655 124 4406482
242 567 5548735
385 694 8703600
705 894 798435
930 179 9333610
346 83 9417442
621 768 953905
490 586 7780155
149 897 7212005
1...

output:

23133220

result:

ok 1 number(s): "23133220"

Test #13:

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

input:

1000 500
474 953 613 122 585 861 627 461 231 466 197 437 807 645 724 259 221 65 312 263 441 895 643 507 159 279 257 801 577 546 160 706 674 840 433 761 921 818 40 862 535 443 396 75 311 836 959 57 986 603 179 133 110 775 990 269 539 858 153 124 529 979 423 241 561 911 151 223 570 275 586 969 49 390 ...

output:

1414024

result:

ok 1 number(s): "1414024"

Test #14:

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

input:

1000 500
229 839 104 538 821 95 707 79 31 77 279 946 889 851 181 165 819 493 129 448 913 371 441 232 278 750 547 432 482 618 998 787 14 987 886 774 97 549 349 425 867 980 974 317 426 451 307 770 140 628 277 629 154 415 595 337 715 374 900 554 395 358 340 465 578 359 195 449 71 898 184 942 382 535 81...

output:

80274

result:

ok 1 number(s): "80274"

Test #15:

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

input:

1000 900
303 676 854 267 542 784 219 315 492 383 576 366 789 242 555 1000 468 98 200 216 324 266 692 647 697 801 271 150 523 274 997 837 912 227 810 97 63 75 182 889 441 167 658 881 546 690 745 999 973 931 396 193 36 888 977 13 322 45 845 323 659 630 940 37 794 645 34 772 562 287 275 662 149 818 524...

output:

212409006

result:

ok 1 number(s): "212409006"

Test #16:

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

input:

1000 900
774 276 770 240 640 925 281 3 267 218 974 220 67 453 839 375 649 927 18 607 390 356 154 294 908 778 370 321 396 787 637 342 939 194 600 760 832 988 195 215 345 817 363 2 263 410 56 478 871 295 877 205 6 458 822 876 316 292 346 786 497 235 179 581 570 834 740 432 931 707 33 986 317 896 369 1...

output:

935960

result:

ok 1 number(s): "935960"

Test #17:

score: 0
Accepted
time: 340ms
memory: 69972kb

input:

500000 4
106205 145911 308784 309818
173026 2126 4270970
129972 318824 3437995
242708 496326 5728595
489769 449454 1317695
19071 12221 2171330
324318 465927 8289370
250365 198547 4247220
113002 439584 9032210
181744 197205 3787265
356860 42040 7483920
266817 265916 5304505
448342 397019 6460605
2770...

output:

9277166

result:

ok 1 number(s): "9277166"

Test #18:

score: 0
Accepted
time: 375ms
memory: 72612kb

input:

500000 6
499257 13498 291931 315623 89166 446105
258016 143233 4788785
329306 370744 4955495
181201 120316 2303280
286403 287884 8301455
101554 109702 5052825
144526 32726 4327630
119467 284351 4910345
241272 389997 2610910
108360 396604 8655470
398856 182059 4203560
499307 173512 4788790
452923 238...

output:

18631380

result:

ok 1 number(s): "18631380"

Test #19:

score: 0
Accepted
time: 764ms
memory: 87468kb

input:

500000 100000
416405 276723 151805 184195 70248 146161 373375 457425 261409 457413 22783 351152 318906 224474 478166 426666 51775 27004 216988 266209 195353 464019 146933 392726 198881 406515 87339 173283 260461 315869 210891 368114 212156 355919 380867 314480 235137 147107 273691 493714 116626 4034...

output:

43477889778

result:

ok 1 number(s): "43477889778"

Test #20:

score: 0
Accepted
time: 693ms
memory: 87424kb

input:

500000 97979
140642 113076 68095 334268 369909 387243 164242 485128 343644 172682 436437 470865 382648 89179 496575 62600 474653 18702 163098 478770 425097 91082 474994 492939 464669 264166 112080 420199 469109 57496 81686 497481 476597 413067 88365 169380 305821 338481 127679 400199 274922 169240 2...

output:

44788672

result:

ok 1 number(s): "44788672"

Test #21:

score: 0
Accepted
time: 872ms
memory: 118820kb

input:

500000 480090
110653 124900 475583 169836 85485 128730 365920 157501 85413 281719 344205 198588 306451 182942 182409 12364 225824 422107 204129 18490 110146 366839 258863 491436 220631 230223 405412 456087 484158 260680 363402 337695 48005 343432 407147 134105 214979 320381 273357 385807 67422 25449...

output:

488204324

result:

ok 1 number(s): "488204324"

Test #22:

score: 0
Accepted
time: 923ms
memory: 118704kb

input:

500000 490000
264535 72499 433762 307268 361790 120295 274361 381547 188972 222139 43411 362972 467936 396577 244084 244071 208810 243178 362410 229709 130756 470269 220737 349336 163545 177643 254628 41149 243527 439991 321840 354696 134626 495822 434133 255512 126909 87976 227245 324677 401572 354...

output:

6577148990

result:

ok 1 number(s): "6577148990"

Test #23:

score: 0
Accepted
time: 442ms
memory: 74304kb

input:

500000 106
94658 92437 336053 327282 32956 173545 47425 343677 250802 375660 323357 92656 262144 465017 4711 482250 465012 125065 247467 318740 227061 390684 420839 323865 490623 473615 269264 446566 351887 134866 192467 309843 211825 295716 132208 314885 497772 5741 446494 306284 186828 331394 4197...

output:

51343248586

result:

ok 1 number(s): "51343248586"

Test #24:

score: 0
Accepted
time: 448ms
memory: 73252kb

input:

500000 13
158609 333540 219399 425174 90641 20269 446657 52386 438693 339454 391906 32767 14379
133521 195146 9123615
143244 220668 1143970
375348 478627 9097280
339863 383491 1847635
34764 426964 8839610
1476 424565 4657135
129907 324031 6920545
440296 363823 3489110
106113 491055 3368785
362255 42...

output:

24000542668

result:

ok 1 number(s): "24000542668"

Test #25:

score: 0
Accepted
time: 1005ms
memory: 123488kb

input:

500000 491111
330041 193079 197316 250636 221756 269821 162035 168251 406035 15500 241553 116226 2017 87811 339439 78366 293298 235730 461487 173454 131781 355773 44292 330264 330363 51806 72560 209278 153461 35885 399817 418689 315236 229072 8372 224377 5740 392573 195655 441392 470995 318189 92274...

output:

20238980522002

result:

ok 1 number(s): "20238980522002"

Test #26:

score: 0
Accepted
time: 838ms
memory: 89408kb

input:

500000 131313
165702 393664 345838 41643 98305 350131 247755 177063 107761 263472 169243 287241 207348 231816 206625 183040 91681 408855 286858 292649 323612 255984 79580 196248 495728 137234 326393 372202 424066 364297 461755 160469 315421 401364 349124 56925 103626 259047 323307 457058 400957 3498...

output:

95944737522

result:

ok 1 number(s): "95944737522"

Test #27:

score: 0
Accepted
time: 331ms
memory: 71708kb

input:

500000 13
82840 424884 136569 258168 24288 137470 89995 336275 251382 728 368120 191575 366194
117076 203293 9574720
406825 306309 3656710
141897 43495 8292085
225457 352956 4875200
262534 40284 5793035
430010 196189 2251555
215909 139745 3617885
245742 202624 13010
177532 170501 1541870
98917 19507...

output:

3863162

result:

ok 1 number(s): "3863162"

Test #28:

score: 0
Accepted
time: 558ms
memory: 81208kb

input:

500000 51511
99471 371535 174146 174999 252215 41386 182734 47120 57443 208285 38793 296635 18974 432400 274904 369845 207758 224479 253606 499031 169444 487 424104 217197 385009 206856 324147 430931 214036 413992 31207 126539 399251 106782 429356 406698 206656 40519 302863 91393 113687 88002 354425...

output:

56447952

result:

ok 1 number(s): "56447952"

Test #29:

score: 0
Accepted
time: 823ms
memory: 116208kb

input:

500000 490000
125945 305326 269912 207424 148481 6455 485157 387553 457482 113374 100101 377411 85060 497092 53706 340742 65200 351093 350696 106920 349438 28556 327679 197623 240110 446447 339668 459655 416834 157282 229116 428468 209935 105676 488417 277639 316507 307487 466520 16950 79197 23866 3...

output:

416483008

result:

ok 1 number(s): "416483008"

Test #30:

score: 0
Accepted
time: 985ms
memory: 116348kb

input:

500000 500000
84330 245772 402991 250141 5604 363698 28210 138716 31288 391084 483602 328596 138932 405509 25377 353811 380790 65991 391612 19490 315385 304280 427788 114898 357007 152775 96308 237413 146265 325603 102990 285721 388641 378680 336417 419519 29709 357031 112369 375439 168984 425198 35...

output:

7677178150814

result:

ok 1 number(s): "7677178150814"

Test #31:

score: 0
Accepted
time: 388ms
memory: 93092kb

input:

500000 2
318064 391717
318064 143782 25
365632 391717 39
143782 133725 59
133725 46760 14
46760 254136 40
254136 490096 31
490096 235449 7
235449 372372 93
372372 82432 23
82432 331118 15
331118 308701 27
308701 201298 36
201298 357074 27
357074 208180 49
208180 499575 37
499575 304091 21
304091 313...

output:

2

result:

ok 1 number(s): "2"

Test #32:

score: 0
Accepted
time: 1096ms
memory: 138880kb

input:

500000 496868
53541 270588 411773 75707 126462 148263 263940 393429 111858 31570 70882 341735 364702 105950 141943 69556 462655 251516 297313 161662 350898 312976 246194 108388 20963 207613 439125 320614 437629 303910 17038 273054 20353 479988 466798 240173 34591 245862 399564 202502 75624 458336 45...

output:

4546171846127314

result:

ok 1 number(s): "4546171846127314"

Test #33:

score: 0
Accepted
time: 700ms
memory: 113668kb

input:

500000 13132
274159 417533 372934 164207 177698 1211 475002 408787 151567 493878 85834 370496 426812 319304 44988 281 287319 44853 433150 45726 38899 408210 16515 118695 354513 412338 136015 120387 318655 145980 218809 368275 121974 467925 297388 69577 460219 57624 398532 483544 316525 145008 53574 ...

output:

2005390732

result:

ok 1 number(s): "2005390732"