QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#208573 | #5828. 游戏 | Williamxzh | 100 ✓ | 312ms | 78044kb | C++14 | 4.2kb | 2023-10-09 19:00:41 | 2023-10-09 19:00:41 |
Judging History
answer
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-loops")
#pragma GCC target("avx2,sse4")
#include <bits/stdc++.h>
#define il inline
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=2e5+5;
int n,Q,fa[N][20],de[N],lg[N];pii mx[N][3];
vector<int> e[N];
il void add(int x,int y){e[x].push_back(y);}
void dfs(int x,int fath){
pii u;fa[x][0]=fath,de[x]=de[fath]+1;
for(int i=0;i<3;++i) mx[x][i]={0,x};
for(int i=1;i<=18;++i) fa[x][i]=fa[fa[x][i-1]][i-1];
for(int y : e[x]){
if(y==fath) continue;
dfs(y,x),u=mx[y][0],++u.fi;
for(int i=0;i<3;++i) if(u>=mx[x][i]) swap(u,mx[x][i]);
}
}
void dfs1(int x,int fath,pii u){
pii v;
for(int i=0;i<3;++i) if(u>=mx[x][i]) swap(u,mx[x][i]);
for(int y : e[x]){
if(y==fath) continue;
v=(mx[x][0].se==mx[y][0].se?mx[x][1]:mx[x][0]),++v.fi,v=max(v,u);
dfs1(y,x,v);
}
}
il int lca(int x,int y){
if(de[x]<de[y]) swap(x,y);
while(de[x]>de[y]) x=fa[x][lg[de[x]-de[y]]-1];
if(x==y) return x;
for(int i=18;i>=0;--i) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
il int jump(int x,int k){
for(int i=18;i>=0;--i) if(de[x]-de[fa[x][i]]<=k) k-=de[x]-de[fa[x][i]],x=fa[x][i];
return x;
}
il int get(int s,int t,int k){
int x=lca(s,t),y=de[s]-de[x],z=de[t]-de[x];
if(s==x) return jump(t,z-k);
if(y>=k) return jump(s,k);
else return jump(t,y+z-k);
}
il bool cmp(int x,int y){
return mx[x][0].fi==mx[y][0].fi?(mx[x][1].fi==mx[y][1].fi?mx[x][2].fi<mx[y][2].fi:mx[x][1].fi<mx[y][1].fi):mx[x][0].fi<mx[y][0].fi;
}
vector<int> f[N];
struct node{
int x,y,z;
il node(){x=y=z=0;}
il node(int x,int y,int z) : x(x),y(y),z(z) {}
}q[N];
vector<pii> g[N];
int tree[N<<2];
il void pushup(int x){tree[x]=(mx[tree[x<<1]][2].fi>=mx[tree[x<<1|1]][2].fi?tree[x<<1]:tree[x<<1|1]);}
il void update(int x,int l,int r,int p,int u){
if(l==r){tree[x]=(mx[u][2].fi>=mx[tree[x]][2].fi?u:tree[x]);return ;}
int mid=(l+r)>>1;
if(p<=mid) update(x<<1,l,mid,p,u);
else update(x<<1|1,mid+1,r,p,u);
pushup(x);
}
int query(int x,int l,int r,int L,int R){
if(l>=L && r<=R) return tree[x];
int mid=(l+r)>>1,ret=0,u;
if(L<=mid){
u=query(x<<1,l,mid,L,R);
if(!ret || mx[ret][2].fi<mx[u][2].fi) ret=u;
}
if(R>mid){
u=query(x<<1|1,mid+1,r,L,R);
if(!ret || mx[ret][2].fi<mx[u][2].fi) ret=u;
}
return ret;
}
int x,y,z,u,v,w,p,a[3],ans[N];
int main(){
//freopen("game.in","r",stdin);
//freopen("game.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<n;++i) scanf("%d%d",&x,&y),add(x,y),add(y,x);
for(int i=1;i<=n;++i) lg[i]=lg[i>>1]+1;
dfs(1,0),dfs1(1,0,{0,0});
for(int i=1;i<=n;++i) f[mx[i][0].fi].push_back(i);
scanf("%d",&Q);
for(int i=1;i<=Q;++i){
scanf("%d%d%d",&x,&y,&z);
u=(x+y-z)>>1,v=(x-y+z)>>1,w=(y+z-x)>>1,a[0]=u,a[1]=v,a[2]=w,q[i]=node(u,v,w);sort(a,a+3);
g[a[2]].push_back({i,a[1]});
}
for(int i=n;~i;--i){
for(int x : f[i]) update(1,0,n,mx[x][1].fi,x);
for(pii x : g[i]) ans[x.fi]=query(1,0,n,x.se,n);
}
for(int i=1;i<=Q;++i){
p=ans[i],x=q[i].x,y=q[i].y,z=q[i].z;
if(mx[p][0].fi>=x && mx[p][1].fi>=y && mx[p][2].fi>=z) printf("%d %d %d\n",get(p,mx[p][0].se,x),get(p,mx[p][1].se,y),get(p,mx[p][2].se,z));
else if(mx[p][0].fi>=x && mx[p][2].fi>=y && mx[p][1].fi>=z) printf("%d %d %d\n",get(p,mx[p][0].se,x),get(p,mx[p][2].se,y),get(p,mx[p][1].se,z));
else if(mx[p][1].fi>=x && mx[p][0].fi>=y && mx[p][2].fi>=z) printf("%d %d %d\n",get(p,mx[p][1].se,x),get(p,mx[p][0].se,y),get(p,mx[p][2].se,z));
else if(mx[p][1].fi>=x && mx[p][2].fi>=y && mx[p][0].fi>=z) printf("%d %d %d\n",get(p,mx[p][1].se,x),get(p,mx[p][2].se,y),get(p,mx[p][0].se,z));
else if(mx[p][2].fi>=x && mx[p][0].fi>=y && mx[p][1].fi>=z) printf("%d %d %d\n",get(p,mx[p][2].se,x),get(p,mx[p][0].se,y),get(p,mx[p][1].se,z));
else if(mx[p][2].fi>=x && mx[p][1].fi>=y && mx[p][0].fi>=z) printf("%d %d %d\n",get(p,mx[p][2].se,x),get(p,mx[p][1].se,y),get(p,mx[p][0].se,z));
}
return 0;
}
详细
Test #1:
score: 10
Accepted
time: 0ms
memory: 22328kb
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:
421 209 365 421 202 420 361 278 175 343 209 473 436 420 57 30 110 146 343 246 7 158 430 47 179 412 116 120 350 435 215 202 378 215 217 365 253 110 126 311 108 73 125 242 175 49 273 378 306 350 344 278 228 360 253 53 262 158 202 36 202 50 110 211 353 406 361 328 439 17 353 423 215 305 406 110 139 7 3...
result:
ok Accepted!
Test #2:
score: 10
Accepted
time: 6ms
memory: 24600kb
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:
1995 1000 761 528 1533 1738 809 1000 1003 870 831 1000 692 1227 898 109 646 726 1995 970 1738 1030 1991 1758 1390 440 1095 339 1053 439 586 692 1702 836 413 471 1574 217 653 1201 1039 1804 664 1039 402 158 1533 174 1001 1533 1343 989 1991 735 1783 1950 1758 1447 1734 1049 1480 409 843 1366 368 562 1...
result:
ok Accepted!
Test #3:
score: 10
Accepted
time: 85ms
memory: 54056kb
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:
87763 127372 167377
result:
ok Accepted!
Test #4:
score: 10
Accepted
time: 90ms
memory: 53492kb
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:
82066 7276 199629
result:
ok Accepted!
Test #5:
score: 10
Accepted
time: 96ms
memory: 50784kb
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:
34411 24423 130978 39355 108717 46584 52145 10301 66653 129196 118391 75453 96028 74366 93926 194867 26201 124636 193249 124776 8021 36173 21360 118748 16928 105792 116603 197158 35115 78006
result:
ok Accepted!
Test #6:
score: 10
Accepted
time: 93ms
memory: 53932kb
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:
145500 71887 100276 156481 3301 65860 134802 99663 157918 126929 74888 4153 79250 75665 19591 31684 118762 29616 77495 79528 148651 49868 110284 99352 12157 122489 51911 82672 126427 64004
result:
ok Accepted!
Test #7:
score: 10
Accepted
time: 312ms
memory: 78044kb
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: 176ms
memory: 54220kb
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 70254 197325 197325 155225 56264 56264 38396 197325 197325 173619 197325 197325 95661 197325 197325 156174 197325 197325 138343 197325 197325 29777 197325 197325 188592 197325 197325 107966 197325 197325 107552 197325 197325 44079 197325 197325 193253 197325 197325 99075 197325 197325 ...
result:
ok Accepted!
Test #9:
score: 10
Accepted
time: 234ms
memory: 56868kb
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:
80097 161600 36567 66894 56002 38634 184795 112119 193267 165046 74246 102483 66610 120520 160376 119681 178802 87450 113149 178393 172202 83964 107997 180100 99848 21334 5957 75873 188561 184300 119888 20580 66285 44224 78138 151916 151223 16594 71093 3957 182002 80938 82137 178243 159894 99825 120...
result:
ok Accepted!
Test #10:
score: 10
Accepted
time: 232ms
memory: 54624kb
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:
46612 23373 84089 74523 11770 103058 113594 160961 4313 25740 40546 64481 184978 63792 71292 163893 1353 78456 130689 166930 162505 166586 3669 94060 21175 41973 74478 134043 168152 30888 3992 90970 93502 17316 118619 100001 77703 49370 42008 95660 168939 168135 55180 38268 109017 100828 50538 16609...
result:
ok Accepted!
Extra Test:
score: 0
Extra Test Passed