QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#88717 | #5828. 游戏 | Appleblue17 | 80 | 942ms | 76484kb | C++14 | 3.4kb | 2023-03-16 21:54:02 | 2023-03-16 21:54:02 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int n,q,ans[N];
vector <int> G[N];
struct dat{
int dis,u,typ;
};
int dep[N],fx[N][20];
dat mx[N],mx2[N],mx3[N];
void upd(int u,dat V){
if(V.dis>mx[u].dis) mx3[u]=mx2[u],mx2[u]=mx[u],mx[u]=V;
else if(V.dis>mx2[u].dis) mx3[u]=mx2[u],mx2[u]=V;
else if(V.dis>mx3[u].dis) mx3[u]=V;
}
void dfs(int u,int fa){
fx[u][0]=fa;
for(int t=1;t<=18;t++) fx[u][t]=fx[fx[u][t-1]][t-1];
dep[u]=dep[fa]+1;
mx[u]=mx2[u]=mx3[u]={0,u,0};
for(int v: G[u]){
if(v==fa) continue;
dfs(v,u);
upd(u,(dat){mx[v].dis+1,mx[v].u,0});
}
}
void dfss(int u,int fa){
for(int v: G[u]){
if(v==fa) continue;
if(mx[u].u!=mx[v].u) upd(v,(dat){mx[u].dis+1,mx[u].u,1});
else upd(v,(dat){mx2[u].dis+1,mx2[u].u,1});
dfss(v,u);
}
}
inline int cal(int x,int y){
return (x && y)?x:(x | y);
}
struct abc{
int typ,a,b,c,num,pos;
}p[N*2];
int id;
bool cmp1(abc X,abc Y){
if(X.a==Y.a) return X.typ<Y.typ;
return X.a>Y.a;
}
bool cmp2(abc X,abc Y){
if(X.b==Y.b) return X.typ<Y.typ;
return X.b>Y.b;
}
int c[N];
inline int lowbit(int x){
return x & (-x);
}
inline void modify(int x,int k){
x++;
while(x) c[x]=cal(c[x],k),x-=lowbit(x);
}
inline void clr(int x){
x++;
while(x) c[x]=0,x-=lowbit(x);
}
inline int query(int x){
x++;
int tot=0;
while(x<=n+1) tot=cal(tot,c[x]),x+=lowbit(x);
return tot;
}
void CDQ(int l,int r){
if(l==r) return ;
int mid=(l+r)>>1;
CDQ(l,mid);
CDQ(mid+1,r);
sort(p+l,p+r+1,cmp2);
for(int i=l;i<=r;i++){
if(p[i].typ==1 && p[i].pos<=mid){
modify(p[i].c,p[i].num);
}
else if(p[i].typ==2 && p[i].pos>mid && !ans[p[i].num]){
ans[p[i].num]=cal(ans[p[i].num],query(p[i].c));
}
}
for(int i=l;i<=r;i++)
if(p[i].typ==1 && p[i].pos<=mid)
clr(p[i].c);
}
int glca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int t=18;t>=0;t--)
if(dep[fx[x][t]]>=dep[y]) x=fx[x][t];
if(x==y) return x;
for(int t=18;t>=0;t--)
if(fx[x][t]!=fx[y][t]) x=fx[x][t],y=fx[y][t];
return fx[x][0];
}
int kthfa(int x,int k){
for(int t=20;t>=0;t--)
if(k>=(1<<t)) x=fx[x][t],k-=1<<t;
return x;
}
int getans(int u,dat V,int dis){
if(!V.typ){
return kthfa(V.u,V.dis-dis);
}
else{
int lc=glca(u,V.u);
if(dis<=dep[u]-dep[lc]){
return kthfa(u,dis);
}
else{
return kthfa(V.u,V.dis-dis);
}
}
}
int sav[N][3],P[N][3];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<n;i++){
int u,v; cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dep[0]=-1;
dfs(1,0);
dfss(1,0);
for(int i=1;i<=n;i++){
p[++id]={1,mx3[i].dis,mx2[i].dis,mx[i].dis,i};
}
cin>>q;
for(int i=1;i<=q;i++){
int x,y,z; cin>>x>>y>>z;
int a=(x+y-z)/2,b=(x+z-y)/2,c=(y+z-x)/2;
sav[i][0]=a,sav[i][1]=b,sav[i][2]=c;
P[i][0]=0,P[i][1]=1,P[i][2]=2;
for(int t=1;t<=3;t++){
if(a>b) swap(a,b),swap(P[i][0],P[i][1]);
if(b>c) swap(b,c),swap(P[i][1],P[i][2]);
}
p[++id]={2,a,b,c,i};
}
sort(p+1,p+id+1,cmp1);
for(int i=1;i<=id;i++) p[i].pos=i;
CDQ(1,id);
for(int i=1;i<=q;i++){
int x=ans[i];
dat V[3];
for(int t=0;t<3;t++){
if(P[i][0]==t) V[t]=mx3[x];
if(P[i][1]==t) V[t]=mx2[x];
if(P[i][2]==t) V[t]=mx[x];
}
int A=getans(x,V[0],sav[i][0]);
int B=getans(x,V[1],sav[i][1]);
int C=getans(x,V[2],sav[i][2]);
cout<<A<<" "<<B<<" "<<C<<'\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 3ms
memory: 12996kb
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:
125 285 94 346 488 386 478 342 285 193 215 149 144 350 360 53 436 17 146 480 6 440 311 451 239 144 342 150 4 230 306 497 356 487 217 456 452 436 361 423 248 328 17 333 285 497 48 356 453 343 328 496 247 211 353 349 270 314 401 114 245 360 177 211 353 406 478 454 80 429 416 50 305 215 406 436 386 346...
result:
ok Accepted!
Test #2:
score: 10
Accepted
time: 14ms
memory: 13280kb
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:
474 1244 1024 44 706 990 1565 1244 1630 1090 1159 1244 134 1840 1973 337 690 1779 798 1262 1738 668 1551 1878 1440 158 200 1533 1454 1028 264 1277 1147 1495 261 1201 1118 1208 1217 1978 31 1277 529 31 1752 1478 1402 1861 1277 1973 1840 515 166 1689 1472 1026 989 1254 307 368 1840 468 523 1081 945 10...
result:
ok Accepted!
Test #3:
score: 10
Accepted
time: 514ms
memory: 47652kb
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:
161686 50151 60815
result:
ok Accepted!
Test #4:
score: 10
Accepted
time: 516ms
memory: 47536kb
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:
21138 148400 122968
result:
ok Accepted!
Test #5:
score: 10
Accepted
time: 525ms
memory: 47744kb
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:
184458 188598 125785 163541 56238 186273 113081 39012 13235 26861 106144 160945 16658 157350 192448 8412 35694 91454 175168 88621 54064 48815 134805 37526 158076 81154 121210 91162 43513 13269
result:
ok Accepted!
Test #6:
score: 10
Accepted
time: 526ms
memory: 47552kb
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:
46013 89402 196644 165333 31595 87543 196600 44966 16436 40657 108839 54522 112974 104457 146338 6011 104277 89585 85385 22715 66829 59562 87964 193634 79717 84041 125351 26594 44088 33136
result:
ok Accepted!
Test #7:
score: 10
Accepted
time: 942ms
memory: 76484kb
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:
17305 162949 100001 129804 100001 61045 5222 120705 100001 100001 79890 116671 64026 105656 100001 13516 100001 128131 100001 156172 41388 177629 100001 5761 25711 200000 68037 175188 154225 1 57460 60359 200000 39640 100001 121712 104028 83446 100001 6718 100001 183956 8968 108150 100001 17865 1000...
result:
ok Accepted!
Test #8:
score: 10
Accepted
time: 857ms
memory: 57712kb
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:
56980 56980 144555 56980 56980 25686 36778 36778 178310 56980 56980 94149 56980 56980 38289 56980 56980 74592 56980 56980 5147 56980 56980 42452 56980 56980 197563 56980 56980 70042 56980 56980 45450 56980 56980 154727 56980 56980 143662 56980 56980 101637 56980 56980 20344 113946 113946 178310 5698...
result:
ok Accepted!
Test #9:
score: 0
Time Limit Exceeded
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:
91209 91828 54836 122282 37725 190275 120030 165504 81583 154175 153528 59038 158254 56702 91361 63905 58984 77065 121326 72487 133533 43623 21411 79690 155825 21012 67566 94623 191109 127302 116351 151586 162356 155985 164569 53591 24962 10321 195976 3649 83124 20602 82777 170043 41684 167969 18246...
result:
Test #10:
score: 0
Time Limit Exceeded
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:
50733 180014 183930 187358 17063 150075 54484 149425 21861 155162 125797 46700 175261 120909 108028 42644 139608 26522 43979 143540 198075 87366 56051 74697 92188 197397 5241 31435 72709 166942 55109 51709 149537 17330 72374 180261 144627 54081 156253 123951 114221 18321 169317 68603 67160 88879 167...