QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#95475#5102. Dungeon CrawlermarcoskAC ✓829ms41796kbC++143.1kb2023-04-09 20:28:352023-04-09 20:28:38

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-09 20:28:38]
  • 评测
  • 测评结果:AC
  • 用时:829ms
  • 内存:41796kb
  • [2023-04-09 20:28:35]
  • 提交

answer

#include <bits/stdc++.h>
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define pb push_back
#define ALL(s) s.begin(),s.end()
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define SZ(s) int(s.size())
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;

struct STree{
	vector<ll> t; int n;
	STree(int n):n(n),t(2*n+5,-1e18){}
	void upd(int p, ll v){
		p+=n;
		for(t[p]=v;p>1;p>>=1) t[p>>1]=max(t[p],t[p^1]);
	}
	ll query(int l, int r){ // [l, r)
		ll res=-1e18;
		for(l+=n,r+=n;l<r;l>>=1,r>>=1){
			if(l&1) res=max(res,t[l++]);
			if(r&1) res=max(res,t[--r]);
		}
		return res;
	}
};

const int K=11, MAXN=1<<K;
vector<ii> g[MAXN];
vector<pair<ii,int>> op[MAXN];
int idd,in[MAXN],sz[MAXN],bad[200010],par[MAXN],n;
ll pt[MAXN],ans[200010],wh[MAXN][MAXN];

int F[K][1<<K],D[1<<K];
void lca_dfs(int x){
	fore(i,0,g[x].size()){
		int y=g[x][i].fst;if(y==F[0][x])continue;
		F[0][y]=x;D[y]=D[x]+1;lca_dfs(y);
	}
}
void lca_init(int rt){
	D[rt]=0;F[0][rt]=-1;
	lca_dfs(rt);
	fore(k,1,K)fore(x,0,n)
		if(F[k-1][x]<0)F[k][x]=-1;
		else F[k][x]=F[k-1][F[k-1][x]];
}
int lca(int x, int y){
	if(D[x]<D[y])swap(x,y);
	for(int k=K-1;k>=0;--k)if(D[x]-(1<<k)>=D[y])x=F[k][x];
	if(x==y)return x;
	for(int k=K-1;k>=0;--k)if(F[k][x]!=F[k][y])x=F[k][x],y=F[k][y];
	return F[0][x];
}
int jump(int x, int k){
	fore(i,0,K) if(k&(1<<i)) x=F[i][x];
	return x;
}

int dfs(int pos, int p=-1, ll d=0){
	sz[pos]=1; in[pos]=idd++; par[pos]=p;
	pt[pos]=d;
	for(auto x:g[pos]) if(x.fst!=p) sz[pos]+=dfs(x.fst,pos,d+x.snd);
	return sz[pos];
}

int has(int x, int y){
	return in[x] <= in[y] && in[y]<in[x]+sz[x];
}

void doit(int s){
	idd=0; dfs(s);
	
	ll tot=0;
	fore(i,0,n) for(auto x:g[i]) tot+=x.snd;
	
	STree st(n);
	fore(i,0,n) st.upd(in[i],pt[i]);
	lca_init(s);
	
	fore(i,0,n) for(auto xx:g[i]){
		int x=xx.fst;
		if(!has(x,i)){
			ll bst=max(st.query(in[i],in[x]), st.query(in[x]+sz[x],in[i]+sz[i]));
			wh[i][x]=bst-2ll*pt[i];
		}
	}
	
	fore(i,0,n) wh[i][i]=st.query(in[i],in[i]+sz[i])-2ll*pt[i];
	
	for(auto pp:op[s]){
		int me=pp.fst.fst, he=pp.fst.snd, id=pp.snd;
		
		//imposible
		if(has(he,me)){
			bad[id]=1;
			continue;
		}
		
		//puedo cualquiera
		if(has(me,he)){
			ans[id]=tot-st.query(0,n);
			continue;
		}
		
		//cualquiera que no vaya desde el lca hasta me
		int lc=lca(me,he);
		int low=jump(me, D[me]-D[lc]-1);
		ll bst=max(st.query(0,in[low]), st.query(in[low]+sz[low],n));
		
		//en el camino desde el lca hasta me, cualquiera sin el subarbol de me
		
		
		//en el subarbol de me + el camino desde el lca a la raiz - lo del medio
		int pre=me,now=me;
		while(now!=lc){
			ll val=wh[now][pre]+2*pt[lc];
			bst=max(bst, val);
			pre=now;
			now=par[now];
		}
		
		ans[id]=tot-bst;
	}
}

int main(){FIN;
	int q; cin>>n>>q;
	fore(i,1,n){
		int x,y,w; cin>>x>>y>>w; x--; y--;
		g[x].pb({y,w}); g[y].pb({x,w});
	}
	
	fore(i,0,q){
		int s,k,t; cin>>s>>k>>t; s--; k--; t--;
		op[s].pb({{k,t},i});
	}
	
	fore(i,0,n) doit(i);
	
	fore(i,0,q){
		if(bad[i])cout<<"impossible\n";
		else cout<<ans[i]<<"\n";
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5732kb

input:

22 5
1 2 7
2 3 5
3 4 8
3 6 6
3 7 3
2 5 6
5 8 2
8 9 11
2 10 16
1 11 12
11 12 4
11 13 9
1 14 25
14 15 4
15 16 5
15 17 6
15 18 1
15 19 8
14 20 7
20 21 9
20 22 17
1 19 9
1 9 19
1 8 9
1 9 8
2 22 11

output:

316
293
293
impossible
314

result:

ok 5 lines

Test #2:

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

input:

100 100
1 2 289384
2 3 930887
2 4 692778
4 5 636916
4 6 747794
4 7 238336
4 8 885387
8 9 760493
8 10 516650
8 11 641422
8 12 202363
8 13 490028
8 14 368691
8 15 520060
8 16 897764
16 17 513927
16 18 180541
16 19 383427
16 20 89173
16 21 455737
16 22 5212
16 23 595369
16 24 702568
16 25 956430
16 26 ...

output:

103526917
103484292
106288816
104379596
104405611
104775512
105434682
105291604
103838430
105371370
104677980
104175650
105894571
104509242
103971939
105376499
105223283
104153426
105082245
105413188
104130613
104800548
106846555
104138329
103769253
105456754
104044745
104385328
106973740
105460460
...

result:

ok 100 lines

Test #3:

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

input:

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

output:

99
78
97
87
88
93

result:

ok 6 lines

Test #4:

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

input:

10 9
9 2 5
9 1 6
9 4 97
9 7 2
9 8 42
9 10 11
9 6 77
9 3 14
9 5 9
4 7 10
7 3 8
8 7 9
1 4 8
10 7 4
7 1 2
10 1 5
10 7 2
8 4 10

output:

352
427
impossible
443
418
427
418
418
407

result:

ok 9 lines

Test #5:

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

input:

9 9
2 3 48
9 5 31
7 3 97
4 3 16
1 7 24
5 3 82
8 2 51
6 4 33
1 2 8
3 6 8
1 6 3
9 5 6
2 6 4
5 6 1
9 6 4
2 8 9
4 9 2

output:

530
643
impossible
530
impossible
561
impossible
595
627

result:

ok 9 lines

Test #6:

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

input:

8 9
1 7 51
7 6 86
2 3 62
8 4 72
5 6 17
4 1 75
3 1 41
2 3 7
5 8 4
6 1 3
8 6 2
4 2 7
8 5 6
2 1 5
7 1 6
6 7 8

output:

551
impossible
524
558
579
impossible
551
705
524

result:

ok 9 lines

Test #7:

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

input:

9 9
5 4 13
9 2 10
1 9 25
7 6 34
4 2 77
3 8 67
8 1 57
6 9 100
6 4 1
4 1 7
3 2 9
4 9 7
7 9 3
6 2 1
2 8 4
8 6 2
6 5 9

output:

517
545
impossible
530
483
517
642
584
impossible

result:

ok 9 lines

Test #8:

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

input:

10 10
2 4 26
9 8 39
4 5 88
6 3 70
7 6 7
10 4 41
8 3 57
1 6 15
5 6 9
2 8 6
3 9 1
5 7 8
4 7 8
7 6 4
2 7 3
6 8 2
5 4 10
4 8 9
1 5 9

output:

impossible
496
529
441
531
415
566
529
441
523

result:

ok 10 lines

Test #9:

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

input:

10 9
3 2 6
2 1 18
8 1 44
1 9 42
6 3 72
10 8 46
7 10 93
5 3 11
4 10 13
7 3 1
8 2 5
7 5 4
5 10 8
3 1 4
6 4 3
10 1 6
5 10 8
2 10 4

output:

impossible
550
584
impossible
483
impossible
504
impossible
489

result:

ok 9 lines

Test #10:

score: 0
Accepted
time: 746ms
memory: 41796kb

input:

2000 199998
126 244 481188299
718 1159 740107180
1327 1250 248943862
977 1092 780169400
826 27 932696654
1668 638 478193038
229 174 176675890
1251 646 843918836
102 1973 593920932
236 218 165399894
760 151 890198591
232 502 10739184
1961 1409 45917915
548 1840 974742709
1096 630 280975617
1110 1048 ...

output:

1266421864327
impossible
1003453161105
1017793822920
1056758437569
impossible
1249128162612
1233756636475
1354563020262
1275484665657
impossible
impossible
1644448395794
impossible
impossible
impossible
1305598243001
1730425595360
1090858373772
1180211385304
1235543994987
1894692656465
impossible
12...

result:

ok 199998 lines

Test #11:

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

input:

1999 199999
1233 1172 270406027
1233 238 118916774
1233 902 452751000
1233 1868 96683385
1233 605 546735354
1233 82 679125014
1233 1132 938320209
1233 1424 561568050
1233 113 835230774
1233 330 63962348
1233 1758 986726048
1233 1006 214588798
1233 88 433116365
1233 1122 412164831
1233 1496 846865689...

output:

1993724469968
1993337272038
1993488034133
1993680602118
1993694627446
1994104485073
1994062829494
1993917179450
1993435921379
1993814292350
1993428850371
1993220985867
1993782751870
1994075401526
1993846887971
1994090631242
1993936573248
1993321397280
1993351664812
1993207502090
1994025398060
199385...

result:

ok 199999 lines

Test #12:

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

input:

1998 200000
1348 321 767897262
732 563 244247276
1747 898 143621738
952 79 216678072
693 645 383457558
1061 1084 597211706
1068 1108 69631436
1493 1279 46833316
370 83 741751233
668 234 400581789
1254 807 277405261
246 71 317177072
1778 1307 117275225
1679 1090 454166908
423 1563 270094514
130 1297 ...

output:

1975372410410
1975372410410
1975935828356
1973304488995
1973667551620
1975779404141
1976066886120
1976572750087
1975072593898
1977014789030
1976101190261
1974138271828
1976530258945
1973684336396
1974554366471
1975605779407
1976303286574
1973805733832
1976072007649
1976514431746
1975901590393
197654...

result:

ok 200000 lines

Test #13:

score: 0
Accepted
time: 655ms
memory: 41196kb

input:

1998 199998
594 1154 556527904
735 443 423596386
1775 1615 848547206
1671 1234 171000231
1249 1663 374475402
1917 1121 196759581
57 938 746868584
419 1221 887950273
27 317 850167013
1705 1846 322466225
1836 1777 477834411
1849 368 867004000
1256 1610 326093012
1818 1283 820339723
318 1062 759021533
...

output:

1995392439974
1995757588621
1993551901352
1997160271122
1994401952822
1995034800943
1995113419987
1996096973937
1996396691787
1995491012221
1994645387960
1992363649700
1996323764542
1994438892340
1993053180618
1994462180483
1996598423828
1993492716164
1993933259456
1995045031681
1995823020651
199724...

result:

ok 199998 lines

Test #14:

score: 0
Accepted
time: 829ms
memory: 41348kb

input:

2000 200000
890 129 1
1213 391 5558532
456 1286 485419380
1284 836 44
660 1033 1
1967 1692 57
1855 607 1
376 1842 1365940
33 659 612
1639 57 40587
1003 201 44446
184 1292 3657
1406 1836 13902332
239 811 519
1331 319 749826
218 1953 6
1981 1964 3
399 1468 27074
600 769 99493262
1527 772 135364
1413 1...

output:

130105184557
130664308004
impossible
impossible
130572294036
136262248567
132268782882
131522790821
impossible
impossible
195732356541
136571824140
impossible
133902865084
198087210081
133285529827
132105222970
133329460037
impossible
133329465092
impossible
130974095425
130664461705
130572294035
13...

result:

ok 200000 lines

Test #15:

score: 0
Accepted
time: 490ms
memory: 36708kb

input:

2000 1
1 2 1000000000
1 3 1000000000
1 4 1000000000
1 5 1000000000
1 6 1000000000
1 7 1000000000
1 8 1000000000
1 9 1000000000
1 10 1000000000
1 11 1000000000
1 12 1000000000
1 13 1000000000
1 14 1000000000
1 15 1000000000
1 16 1000000000
1 17 1000000000
1 18 1000000000
1 19 1000000000
1 20 10000000...

output:

3997000000000

result:

ok single line: '3997000000000'

Test #16:

score: 0
Accepted
time: 520ms
memory: 37456kb

input:

2000 10000
180 898 89933
180 402 94
1651 1978 81813
180 1751 888228132
1077 180 27685083
180 1060 1
180 1364 8058
891 180 551
571 180 9622824
1448 180 10
1625 180 100
180 589 1
394 1712 1
180 256 6783346
414 1323 9
730 180 515
1472 180 1
453 180 3773589
1879 180 1
180 1378 96
180 1537 810641
180 125...

output:

203980410655
204049851467
204049908386
204049899759
204046341687
204049898312
204047592926
203540720521
204049908495
204049899089
204049908508
204049902864
204049905993
204049900884
204049908407
204049908506
204049035506
204049903756
204049908508
204049908508
204049908508
204043615125
204047951190
2...

result:

ok 10000 lines

Test #17:

score: 0
Accepted
time: 502ms
memory: 37588kb

input:

1978 10000
1889 707 3446042
940 201 787264
320 530 1
384 1335 9
1240 573 29465949
1386 1057 326096
1480 1315 93058261
1102 1859 714
1880 427 1
1102 695 1
598 926 1
1798 1394 8
1163 1000 272812
1315 158 18777779
335 387 8203
1302 1240 54
1569 335 253898040
1346 1824 21947201
1102 1720 6
1057 1248 749...

output:

182382194473
182760498808
181884622285
182767131929
182750533270
183362723595
182731182731
183310694189
182755949668
182722084400
182382235729
182755858463
182106594742
182726172939
182087778648
182766416644
182758294562
182720967383
182473853665
182755948088
183310756861
182451480636
182451486002
1...

result:

ok 10000 lines

Test #18:

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

input:

6 9
1 2 1
2 3 1
1 4 2000
2 5 5000
3 6 8000
4 1 3
5 1 3
6 1 3
4 3 1
5 3 1
6 3 1
2 4 6
1 5 6
1 6 5

output:

20002
17003
impossible
impossible
17005
17003
22003
22002
25003

result:

ok 9 lines

Test #19:

score: 0
Accepted
time: 565ms
memory: 37576kb

input:

2000 10000
1374 1406 171121
529 147 76
1419 179 2
1913 314 5928
772 1768 871
1809 1434 14978
304 867 33909
613 1267 643
579 1575 441086863
954 1628 199
637 514 24
1105 1201 410
946 828 850
1028 629 95496
794 1668 5139
1471 1146 27
500 654 1863190
1006 794 29256
25 887 272340
966 471 96
303 1890 8899...

output:

impossible
129013534188
impossible
139592478932
168707270454
impossible
impossible
213643633814
impossible
152956304222
177219440395
impossible
176555757699
183717875187
159103517800
170550798505
impossible
impossible
144257517764
141735131233
123067707906
152762288328
151029434818
impossible
138947...

result:

ok 10000 lines

Test #20:

score: 0
Accepted
time: 416ms
memory: 37232kb

input:

1996 10000
59 233 25077562
1226 998 68480
442 1909 964
302 1728 68702601
1022 276 75822
739 1190 2065150
1803 1146 2517
561 1473 45
52 379 1
277 470 88019
867 859 11763126
167 1033 975175468
1291 463 61
1210 303 858
1879 652 61651
436 238 112462557
1799 81 13718
295 1255 5790325
1642 1806 350871208
...

output:

212629172974
212425245241
212627530398
212191899504
212093645571
212633083827
212733787356
212852651413
212644232711
211690644080
212733725683
212302994429
212711891397
212059999422
212732606585
210988964926
212362700241
212546678735
212729098689
212651334235
212586153248
210763052308
212317295461
2...

result:

ok 10000 lines

Test #21:

score: 0
Accepted
time: 574ms
memory: 37620kb

input:

1998 10000
863 1521 2278
862 476 57
975 1396 2558359
502 8 851298
1308 178 8510
1736 720 58348
390 1115 357
1775 366 2602
1718 1747 5
1884 553 2764
1864 921 1
1672 654 3
1265 948 13795446
528 1618 939
1851 1568 18724092
1238 1912 2289
819 1772 618
1318 455 80
160 1046 428386
1008 1615 79779915
884 1...

output:

188524321860
188459301950
188523253691
188523500670
188280316699
188506435186
188510684450
188220540690
188517900899
188519088924
188505926020
187792474828
188517825924
188514315427
188511627014
188406079966
188378351609
187534795044
188741512335
188419202729
187706668157
188489471102
188519205214
1...

result:

ok 10000 lines

Test #22:

score: 0
Accepted
time: 349ms
memory: 38600kb

input:

2000 2
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
10 11 1000000000
11 12 1000000000
12 13 1000000000
13 14 1000000000
14 15 1000000000
15 16 1000000000
16 17 1000000000
17 18 1000000000
18 19 1000000000
19 2...

output:

1999000000000
impossible

result:

ok 2 lines

Extra Test:

score: 0
Extra Test Passed