QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#88364 | #5828. 游戏 | myee | 100 ✓ | 541ms | 66036kb | C++11 | 4.1kb | 2023-03-16 08:32:34 | 2023-03-16 08:32:36 |
Judging History
answer
#include <bits/stdc++.h>
typedef unsigned uint;
typedef long long llt;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _min(T&a,T b){return b<a?(a=b,true):false;}
template<typename T>bol _max(T&a,T b){return a<b?(a=b,true):false;}
inline uint lowbit(uint v){return v&-v;}
std::vector<uint>Way[200005];
std::vector<std::pair<uint,uint> >Dist[200005];
std::pair<uint,uint>MaxDist[200005];
uint Siz[200005],Dep[200005],Heavy[200005],Fath[200005],Dfn[200005],Rot[200005],End[200005],Back[200005],cnt;
voi dfs1(uint p,uint f){
Siz[p]=1,Heavy[p]=-1,Fath[p]=f;
for(auto s:Way[p])if(s!=f){
Dep[s]=Dep[p]+1,dfs1(s,p),Siz[p]+=Siz[s],Dist[p].push_back({MaxDist[s].first+1,MaxDist[s].second});
if(!~Heavy[p]||Siz[Heavy[p]]<Siz[s])Heavy[p]=s;
}
if(Dist[p].empty())Dist[p].push_back({0,p});
MaxDist[p]=*std::max_element(Dist[p].begin(),Dist[p].end());
}
voi dfs2(uint p,uint r){
std::sort(Dist[p].begin(),Dist[p].end()),std::reverse(Dist[p].begin(),Dist[p].end());
Back[Dfn[p]=cnt++]=p,Rot[p]=r;
if(~Heavy[p]){
for(auto s:Way[p])if(s!=Fath[p])
Dist[s].push_back(MaxDist[s].second==Dist[p][0].second?
std::pair<uint,uint>{Dist[p][1].first+1,Dist[p][1].second}:
std::pair<uint,uint>{Dist[p][0].first+1,Dist[p][0].second});
dfs2(Heavy[p],r);for(auto s:Way[p])if(s!=Heavy[p]&&s!=Fath[p])dfs2(s,s);
}
End[p]=cnt;
}
uint lca(uint u,uint v){
while(Rot[u]!=Rot[v]){
if(Dep[Rot[u]]<Dep[Rot[v]])std::swap(u,v);
u=Fath[Rot[u]];
}
return Dep[u]<Dep[v]?u:v;
}
uint kstep(uint u,uint v,uint k){
uint r=lca(u,v);
if(Dep[u]+Dep[v]-Dep[r]*2<k)return-1;
if(Dep[u]-Dep[r]>=k){
while(true){
if(Dfn[u]-Dfn[Rot[u]]>=k)return Back[Dfn[u]-k];
k-=Dfn[u]-Dfn[Rot[u]]+1,u=Fath[Rot[u]];
}
}
else{
k=Dep[u]+Dep[v]-Dep[r]*2-k;
while(true){
if(Dfn[v]-Dfn[Rot[v]]>=k)return Back[Dfn[v]-k];
k-=Dfn[v]-Dfn[Rot[v]]+1,v=Fath[Rot[v]];
}
}
return-1;
}
uint X[200005],Y[200005],Z[200005];
uint Max[200005],Mid[200005],Min[200005];
namespace BIT{
std::pair<uint,uint>A[200005];
voi chg(uint p,std::pair<uint,uint>v){
p=200001-p;while(p<=200001)_max(A[p],v),p+=lowbit(p);
}
std::pair<uint,uint>find(uint p){
std::pair<uint,uint>v;p=200001-p;
while(p)_max(v,A[p]),p-=lowbit(p);
return v;
}
}
uint Ans[200005];
uint P1[200005],P2[200005];
int main(){
#ifdef MYEE
freopen("QAQ.in","r",stdin);
freopen("QAQ.out","w",stdout);
#else
#endif
uint n,q;scanf("%u",&n);
for(uint i=1,u,v;i<n;i++)scanf("%u%u",&u,&v),Way[--u].push_back(--v),Way[v].push_back(u);
dfs1(0,-1),Dist[0].push_back({0,0}),dfs2(0,0);
for(uint i=0;i<n;i++)Dist[i].push_back({0,i}),P1[i]=i;
scanf("%u",&q);
for(uint i=0,x,y,z;i<q;i++)
scanf("%u%u%u",&x,&y,&z),X[i]=(x+y-z)/2,Y[i]=(x-y+z)/2,Z[i]=(-x+y+z)/2,P2[i]=i,
Max[i]=std::max({X[i],Y[i],Z[i]}),Min[i]=std::min({X[i],Y[i],Z[i]}),Mid[i]=X[i]+Y[i]+Z[i]-Max[i]-Min[i];
std::sort(P1,P1+n,[&](uint a,uint b){return Dist[a][0]<Dist[b][0];});
std::sort(P2,P2+q,[&](uint a,uint b){return Max[a]<Max[b];});
for(uint i=n,j=q;j;){
if(!i||Max[P2[j-1]]>Dist[P1[i-1]][0].first)
j--,Ans[P2[j]]=BIT::find(Mid[P2[j]]).second;
else
i--,BIT::chg(Dist[P1[i]][1].first,{Dist[P1[i]][2].first,P1[i]});
}
for(uint i=0;i<q;i++){
uint x=X[i],y=Y[i],z=Z[i],p=Ans[i];
std::vector<std::pair<uint,uint> >V{Dist[p][2],Dist[p][1],Dist[p][0]};
while(x>V[0].first||y>V[1].first||z>V[2].first)std::next_permutation(V.begin(),V.end());
// printf("%u %u %u\n",x,y,z);
// printf("%u %u %u\n",V[0].first,V[1].first,V[2].first);
printf("%u %u %u\n",kstep(p,V[0].second,x)+1,kstep(p,V[1].second,y)+1,kstep(p,V[2].second,z)+1);
}
return 0;
}
/*
g++ game.cpp -o game -std=c++11 -Wall -DMYEE
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 7ms
memory: 13076kb
input:
500 279 196 182 105 400 14 278 217 198 411 379 318 120 421 314 95 437 325 23 433 71 485 192 154 90 224 180 71 328 93 183 101 404 349 223 285 492 100 366 480 29 328 200 448 365 156 226 231 129 167 246 273 171 452 284 6 131 471 229 90 480 48 448 157 240 221 7 36 401 200 255 438 436 110 281 489 388 258...
output:
116 209 456 116 202 190 146 278 136 308 209 28 39 239 152 291 110 361 308 246 390 203 430 49 439 412 421 73 350 401 487 202 366 487 217 456 371 110 125 423 108 120 126 242 136 47 273 366 413 350 454 327 171 360 371 53 211 203 202 424 47 50 110 262 353 290 146 328 179 229 353 311 487 305 290 110 139 ...
result:
ok Accepted!
Test #2:
score: 10
Accepted
time: 3ms
memory: 13320kb
input:
2000 643 1871 689 23 1822 1443 1031 1027 1655 845 189 771 1561 498 19 1778 576 1080 904 717 1690 291 1387 1077 398 811 1310 1231 645 1291 480 927 330 170 1464 1057 1033 894 1308 288 1292 1529 1212 122 1108 401 89 1118 1058 1088 1764 1314 981 1255 1893 864 180 1887 1903 843 734 1412 883 1013 1739 124...
output:
1828 1000 175 101 1533 1242 653 1000 1105 870 769 1000 692 1343 1533 1285 646 120 1828 970 1242 1563 1991 727 1620 440 836 1436 1053 308 29 692 1414 1095 84 195 1108 217 809 1348 1039 1001 562 1039 977 286 1533 1257 1804 1533 1480 989 1846 666 652 1950 1672 1848 1734 1948 1343 409 105 1458 368 664 1...
result:
ok Accepted!
Test #3:
score: 10
Accepted
time: 330ms
memory: 39440kb
input:
200000 56968 132021 105656 107536 123627 58349 119191 138198 133708 142638 114350 24980 137784 40346 124158 130204 80684 183207 78156 94449 21893 157560 54464 73571 145830 57756 160288 32120 178632 142663 26565 185985 70576 24906 32217 115826 185756 137673 54280 179613 77826 144447 66005 29955 11745...
output:
183588 127372 141391
result:
ok Accepted!
Test #4:
score: 10
Accepted
time: 334ms
memory: 39484kb
input:
200000 41999 100683 85781 129266 122431 179332 162416 44814 24405 42267 154161 12483 178049 159964 67625 152391 133072 25866 178005 14695 94384 170290 54701 40323 66280 128515 159022 55057 14985 12920 182805 40659 173117 67973 99771 26102 198919 94543 23608 187601 61125 5759 89437 47647 18142 192402...
output:
30648 7276 95506
result:
ok Accepted!
Test #5:
score: 10
Accepted
time: 313ms
memory: 39820kb
input:
200000 195072 75458 31991 127114 60943 49502 186375 1130 45394 147217 168455 84307 132752 188952 101108 130004 107490 22003 16275 187645 111002 42669 138880 137115 112688 172751 81697 99037 166996 18495 2234 56119 170807 101349 105736 23180 148159 40863 136678 11849 190707 91245 61779 120740 157115 ...
output:
107898 24423 35469 39355 49857 70450 43197 10301 17387 188745 112648 172547 28667 74366 89391 47753 111291 33917 86727 124776 193560 181288 21360 193823 11243 105792 168605 40218 35115 97478
result:
ok Accepted!
Test #6:
score: 10
Accepted
time: 332ms
memory: 39624kb
input:
200000 48556 78408 155026 9376 8983 61211 150393 85068 90892 109283 75746 89742 6760 187245 168658 130735 68602 127646 60802 149828 22898 59471 172845 100274 42303 190696 7612 134905 94702 59800 129633 192496 19903 64869 51318 63358 34692 66030 98535 176606 153647 177529 157903 147292 106273 107278 ...
output:
160968 71887 172972 175224 3301 155718 136255 99663 8719 197332 74888 15491 147837 75665 40179 61618 118762 187886 54450 79528 148651 84433 110284 125308 99168 122489 43978 142520 126427 172234
result:
ok Accepted!
Test #7:
score: 10
Accepted
time: 290ms
memory: 66036kb
input:
200000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
54356 200000 137052 200000 170197 131241 84517 200000 179296 183330 163219 200000 158370 200000 194345 85385 171870 200000 143829 200000 85216 200000 122372 28132 200000 25711 157674 200000 179037 24813 200000 197101 57460 117928 178289 200000 200000 179418 195973 22762 116045 200000 100818 200000 1...
result:
ok Accepted!
Test #8:
score: 10
Accepted
time: 431ms
memory: 45708kb
input:
200000 5732 55198 128966 25317 114737 116391 150003 18274 43867 70745 76222 4169 55976 114951 198396 72896 38647 19711 12756 172119 73197 117994 117512 14177 130965 126990 119440 183341 142023 60829 111893 57350 122754 123305 36525 79077 36447 91967 135405 170456 165839 147481 66074 175822 22238 264...
output:
197325 197325 4704 197325 197325 10591 56264 56264 38396 197325 197325 109303 197325 197325 79504 197325 197325 99289 197325 197325 69799 197325 197325 174490 197325 197325 126621 197325 197325 140463 197325 197325 167534 197325 197325 102608 197325 197325 12754 197325 197325 186281 197325 197325 15...
result:
ok Accepted!
Test #9:
score: 10
Accepted
time: 541ms
memory: 45612kb
input:
200000 185063 17064 180987 114492 88071 71803 158363 135918 60910 54848 97338 6734 192937 9410 49617 199068 82499 63554 188791 188152 178767 40866 11304 27212 144234 138097 42236 3946 103355 12683 50992 20598 145723 48620 11709 115688 123172 121379 70541 130844 147827 39431 139372 61280 42705 54015 ...
output:
16852 161600 144003 147087 56002 142950 104657 112119 167698 134920 74246 195552 179029 120520 174842 151828 178802 52714 139667 178393 173324 196768 107997 93428 155312 21334 5823 94741 188561 160574 102834 20580 117724 152664 78138 113665 112847 16594 9478 122793 182002 61063 122944 178243 135823 ...
result:
ok Accepted!
Test #10:
score: 10
Accepted
time: 474ms
memory: 45740kb
input:
200000 197244 185999 18639 124754 154223 12099 53676 167616 22710 22294 150412 66132 19320 75478 170410 122661 130961 175554 171586 85572 188386 81238 120249 117687 43214 126266 8744 165654 164725 189519 124144 170329 86605 100197 130545 17030 113301 96665 67733 187286 37846 146399 75352 117550 3235...
output:
77819 23373 20019 95761 11770 131379 2614 160961 93061 188210 40546 191755 41838 63792 156254 179500 1353 26124 85691 166930 65243 88067 3669 192149 143997 41973 105686 137988 168152 59440 73735 90970 182873 112218 118619 42991 92721 49370 7976 95660 168939 35969 17492 38268 22990 172124 50538 86583...
result:
ok Accepted!
Extra Test:
score: 0
Extra Test Passed