QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#90793 | #5828. 游戏 | SoyTony | 100 ✓ | 501ms | 85732kb | C++14 | 5.5kb | 2023-03-25 12:13:42 | 2023-03-25 12:13:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int maxn=2e5+10;
#define val first
#define id second
inline int read(){
int x=0,w=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return x*w;
}
int n,m;
vector<int> E[maxn];
int fa[maxn],dep[maxn],siz[maxn],son[maxn],F[maxn][19];
int top[maxn],dfn[maxn],dfncnt;
pii mx[maxn][3];
vector<int> V;
void dfs1(int u,int f,int d){
fa[u]=f,dep[u]=d,siz[u]=1,mx[u][0]=make_pair(0,u);
F[u][0]=fa[u];
for(int k=1;(1<<k)<=dep[u];++k) F[u][k]=F[F[u][k-1]][k-1];
int maxson=-1;
for(int v:E[u]){
if(v==f) continue;
dfs1(v,u,d+1);
siz[u]+=siz[v];
if(siz[v]>maxson) maxson=siz[v],son[u]=v;
if(mx[v][0].val+1>mx[u][0].val){
mx[u][2]=mx[u][1],mx[u][1]=mx[u][0],mx[u][0]=make_pair(mx[v][0].val+1,mx[v][0].id);
}
else if(mx[v][0].val+1>mx[u][1].val){
mx[u][2]=mx[u][1],mx[u][1]=make_pair(mx[v][0].val+1,mx[v][0].id);
}
else if(mx[v][0].val+1>mx[u][2].val){
mx[u][2]=make_pair(mx[v][0].val+1,mx[v][0].id);
}
}
}
void dfs2(int u,int t){
top[u]=t,dfn[u]=++dfncnt;
if(!son[u]) return;
dfs2(son[u],t);
for(int v:E[u]){
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
inline int get_kthfa(int u,int k){
for(int i=0;(1<<i)<=k;++i){
if(k&(1<<i)) u=F[u][i];
}
return u;
}
inline int get_LCA(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]]) swap(u,v);
v=fa[top[v]];
}
if(dep[u]>dep[v]) swap(u,v);
return u;
}
inline int get_dis(int u,int v){
int lca=get_LCA(u,v);
return dep[u]+dep[v]-dep[lca]*2;
}
void get_tri(int u){
for(int v:E[u]){
if(v==fa[u]) continue;
for(int k=0;k<=2;++k){
if(mx[u][k].id==mx[v][0].id) continue;
if(mx[u][k].val+1>mx[v][0].val){
mx[v][2]=mx[v][1],mx[v][1]=mx[v][0],mx[v][0]=make_pair(mx[u][k].val+1,mx[u][k].id);
}
else if(mx[u][k].val+1>mx[v][1].val){
mx[v][2]=mx[v][1],mx[v][1]=make_pair(mx[u][k].val+1,mx[u][k].id);
}
else if(mx[u][k].val+1>mx[v][2].val){
mx[v][2]=make_pair(mx[u][k].val+1,mx[u][k].id);
}
break;
}
get_tri(v);
}
}
struct node{
int a,b,c;
int x,y,z;
bool type,mark;
int ID;
}q[maxn<<1];
int tot;
int ct[maxn];
bool cmp_a(node X,node Y){
if(X.a==Y.a){
if(X.b==Y.b){
if(X.c==Y.c) return X.type<Y.type;
return X.c>Y.c;
}
return X.b>Y.b;
}
return X.a>Y.a;
}
bool cmp_b(node X,node Y){
if(X.b==Y.b){
if(X.c==Y.c) return X.type<Y.type;
return X.c>Y.c;
}
return X.b>Y.b;
}
bool cmp_id(node X,node Y){
if(X.type==Y.type) return X.ID<Y.ID;
return X.type>Y.type;
}
#define mid ((l+r)>>1)
set<pii> S;
void cdq(int l,int r){
if(l==r) return;
cdq(l,mid),cdq(mid+1,r);
int i=l,j=mid+1;
// printf("[%d,%d]\n",l,r);
int mx=-1,mxid=0;
while(i<=mid&&j<=r){
// printf("(%d %d)\n",i,j);
if(q[i].b<q[j].b){
if(q[j].type&&!q[j].mark){
if(q[j].c<=mx) ct[q[j].ID]=mxid,q[j].mark=1;
}
++j;
}
else{
if(!q[i].type&&q[i].c>mx) mx=q[i].c,mxid=q[i].ID;
++i;
}
}
while(j<=r){
if(q[j].type&&!q[j].mark){
if(q[j].c<=mx) ct[q[j].ID]=mxid,q[j].mark=1;
}
++j;
}
inplace_merge(q+l,q+mid+1,q+r+1,cmp_b);
}
inline int calc(int x,int y,int d){
//get z \in (x,y) (x,z)=d
if(!d) return x;
int lca=get_LCA(x,y);
if(lca==x){
return get_kthfa(y,dep[y]-dep[x]-d);
}
else if(lca==y){
return get_kthfa(x,d);
}
else{
if(d<=dep[x]-dep[lca]) return get_kthfa(x,d);
else return get_kthfa(y,dep[x]+dep[y]-2*dep[lca]-d);
}
}
int main(){
n=read();
for(int i=1;i<n;++i){
int u=read(),v=read();
E[u].push_back(v),E[v].push_back(u);
}
dfs1(1,0,0);
dfs2(1,1);
get_tri(1);
for(int i=1;i<=n;++i){
++tot;
q[tot].a=mx[i][0].val,q[tot].b=mx[i][1].val,q[tot].c=mx[i][2].val;
q[tot].type=0,q[tot].ID=i;
}
m=read();
for(int i=1;i<=m;++i){
++tot;
q[tot].x=read(),q[tot].y=read(),q[tot].z=read();
V.clear();
V.push_back((q[tot].x+q[tot].y-q[tot].z)/2);
V.push_back((q[tot].x+q[tot].z-q[tot].y)/2);
V.push_back((q[tot].y+q[tot].z-q[tot].x)/2);
sort(V.begin(),V.end());
q[tot].a=V[2],q[tot].b=V[1],q[tot].c=V[0];
q[tot].type=1,q[tot].mark=0,q[tot].ID=i;
}
sort(q+1,q+tot+1,cmp_a);
cdq(1,tot);
sort(q+1,q+tot+1,cmp_id);
for(int i=1;i<=m;++i){
int now[4];
now[1]=calc(ct[i],mx[ct[i]][0].id,q[i].a);
now[2]=calc(ct[i],mx[ct[i]][1].id,q[i].b);
now[3]=calc(ct[i],mx[ct[i]][2].id,q[i].c);
sort(now+1,now+4);
do{
if(get_dis(now[1],now[2])==q[i].x&&get_dis(now[1],now[3])==q[i].y){
printf("%d %d %d\n",now[1],now[2],now[3]);
break;
}
}while(next_permutation(now+1,now+4));
}
return 0;
}
详细
Test #1:
score: 10
Accepted
time: 2ms
memory: 8436kb
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:
93 175 456 421 47 239 361 278 175 238 136 473 39 239 152 132 110 361 238 281 7 203 125 202 403 39 421 120 350 435 215 202 378 487 217 456 13 110 125 423 248 328 430 240 175 202 443 378 413 350 454 278 228 360 13 148 211 429 49 36 202 50 110 211 353 406 361 328 439 17 169 113 215 305 406 110 360 431 ...
result:
ok Accepted!
Test #2:
score: 10
Accepted
time: 3ms
memory: 8776kb
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:
650 1152 1948 528 898 1026 1039 1152 1400 555 356 1152 692 1343 1533 1285 1111 1118 798 1262 1738 1563 1991 727 1277 270 1095 98 1968 439 29 692 1414 464 413 195 176 910 809 89 572 1001 664 572 722 158 1533 174 1001 1533 1343 989 1991 735 652 1950 1672 1848 1279 1220 1343 409 105 1458 368 664 1149 1...
result:
ok Accepted!
Test #3:
score: 10
Accepted
time: 203ms
memory: 49456kb
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:
174691 1521 23174
result:
ok Accepted!
Test #4:
score: 10
Accepted
time: 248ms
memory: 49580kb
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:
65084 113267 192812
result:
ok Accepted!
Test #5:
score: 10
Accepted
time: 210ms
memory: 49704kb
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:
109618 17388 92384 12535 127432 62292 91674 39369 35469 30540 126059 14696 141664 72351 146163 11984 30205 182528 65761 166561 115982 19845 53008 3787 131060 24418 100878 146188 84411 139719
result:
ok Accepted!
Test #6:
score: 10
Accepted
time: 221ms
memory: 49516kb
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:
181745 194891 117235 105797 173570 81522 3364 22086 157918 126929 139436 4472 147837 75665 40179 31684 19769 84929 85782 60520 171387 49868 110284 99352 46632 164007 62199 142520 126427 172234
result:
ok Accepted!
Test #7:
score: 10
Accepted
time: 383ms
memory: 85732kb
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:
182696 37052 100000 70197 100000 138956 194779 79296 100000 100000 120111 83330 135975 94345 100000 186485 100000 71870 100000 43829 158613 22372 100000 194240 174290 1 131964 175188 154225 1 142541 139642 1 160361 100000 78289 95973 116555 100000 193283 100000 16045 191033 91851 100000 182136 10000...
result:
ok Accepted!
Test #8:
score: 10
Accepted
time: 367ms
memory: 61228kb
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 145627 145627 192226 36778 36778 178310 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 145627 145627 71073 197325 197325 186281 197325 197325 ...
result:
ok Accepted!
Test #9:
score: 10
Accepted
time: 501ms
memory: 61280kb
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:
5086 47995 65911 122282 37725 190275 120030 165504 81583 21352 1327 101769 176902 21071 153201 91014 14719 13809 43244 58010 165460 55889 86134 20618 27615 143236 60183 49099 12178 191094 197061 32997 77274 27576 102616 126281 132981 70384 55991 10690 40225 43313 82777 170043 41684 197779 162894 125...
result:
ok Accepted!
Test #10:
score: 10
Accepted
time: 444ms
memory: 61168kb
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:
52953 115995 20019 95761 156955 99574 2614 160961 93061 52821 146957 191755 41838 63792 156254 145651 155074 78456 58258 144129 162505 166586 3669 94060 169597 31844 74478 137988 168152 59440 73735 106440 172760 11066 19691 100001 160854 8619 7976 95660 185898 38381 17492 146460 171987 172124 104506...
result:
ok Accepted!
Extra Test:
score: 0
Extra Test Passed