QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#88921 | #5828. 游戏 | Larunatrecy | 100 ✓ | 276ms | 69492kb | C++14 | 3.5kb | 2023-03-17 22:19:34 | 2023-03-17 22:19:38 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
struct edge
{
int y,next;
}e[2*N];
int link[N],t=0;
void add(int x,int y)
{
e[++t].y=y;
e[t].next=link[x];
link[x]=t;
}
namespace tree
{
int dep[N],st[2*N][20],tot=0;
int lg[2*N],dfn[N];
void dfs(int x,int pre)
{
st[++tot][0]=x;
dfn[x]=tot;
for(int i=link[x];i;i=e[i].next)
{
int y=e[i].y;
if(y==pre)continue;
dep[y]=dep[x]+1;
dfs(y,x);
st[++tot][0]=x;
}
}
inline int Min(int x,int y)
{
return dep[x]<dep[y]?x:y;
}
void Build()
{
dfs(1,0);
for(int i=2;i<=tot;i++)lg[i]=lg[i>>1]+1;
for(int k=1;k<=lg[tot];k++)
for(int i=1;i+(1<<k)-1<=tot;i++)
st[i][k]=Min(st[i][k-1],st[i+(1<<(k-1))][k-1]);
}
inline int LCA(int x,int y)
{
x=dfn[x];y=dfn[y];
if(x>y)swap(x,y);
int k=lg[y-x+1];
return Min(st[x][k],st[y-(1<<k)+1][k]);
}
inline int dist(int x,int y)
{
return dep[x]+dep[y]-2*dep[LCA(x,y)];
}
}
int st,ed;
int n,m;
int A[N],B[N],fa[N];
void dfs(int x,int pre,int *D)
{
for(int i=link[x];i;i=e[i].next)
{
int y=e[i].y;
if(y==pre)continue;
fa[y]=x;
D[y]=D[x]+1;
dfs(y,x,D);
}
}
bool ins[N];
int seq[N];
int h[N];
void dfs2(int x,int pre)
{
h[x]=0;
for(int i=link[x];i;i=e[i].next)
{
int y=e[i].y;
if(ins[y]||y==pre)continue;
dfs2(y,x);
h[x]=max(h[x],h[y]+1);
}
}
int qoj[N],dfn[N];
int cnt=0;
void dfs3(int x,int pre)
{
qoj[++cnt]=x;
dfn[x]=cnt;
for(int i=link[x];i;i=e[i].next)
{
int y=e[i].y;
if(ins[y]||y==pre)continue;
if(h[x]==h[y]+1)
{
dfs3(y,x);
return;
}
}
}
int mx[N][20];
int lg[N];
inline int Max(int x,int y){return h[x]>h[y]?x:y;}
int x,y,z;
int query(int l,int r)
{
int k=lg[r-l+1];
return Max(mx[l][k],mx[r-(1<<k)+1][k]);
}
int dft[N];
bool check(int a,int b,int c)
{
if(b==0)
{
x=seq[1];
y=seq[a+1];
z=seq[a+c+1];
return 1;
}
int l=a+1,r=m-c;
if(l>r)return 0;
int o=query(l,r);
if(h[o]<b)return 0;
x=seq[dft[o]-a];
y=qoj[dfn[o]+b];
z=seq[dft[o]+c];
return 1;
}
bool check(int x,int y,int z,int u,int v,int w)
{
if(tree::dist(x,y)!=u)return 0;
if(tree::dist(x,z)!=v)return 0;
if(tree::dist(z,y)!=w)return 0;
return 1;
}
int main()
{
cin>>n;
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d %d",&u,&v);
add(u,v);
add(v,u);
}
tree::Build();
dfs(1,0,A);
for(int i=1;i<=n;i++)
if(A[i]>A[st])st=i;
fa[st]=0;
dfs(st,0,B);
for(int i=1;i<=n;i++)
if(B[i]>B[ed])ed=i;
int o=ed;
while(o)
{
ins[o]=1;
seq[++m]=o;
dft[o]=m;
o=fa[o];
}
for(int i=1;i<=m;i++)
{
dfs2(seq[i],0);
dfs3(seq[i],0);
mx[i][0]=seq[i];
}
for(int i=2;i<=m;i++)lg[i]=lg[i>>1]+1;
for(int k=1;k<=lg[m];k++)
for(int i=1;i+(1<<k)-1<=m;i++)
mx[i][k]=Max(mx[i][k-1],mx[i+(1<<(k-1))][k-1]);
int q;
cin>>q;
while(q--)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
int u=a,v=b,w=c;
bool flag=0;
int d=(a+b+c)/2;
a=d-a;b=d-b;c=d-c;
if(!flag)flag|=check(a,b,c);
if(!flag)flag|=check(a,c,b);
if(!flag)flag|=check(b,a,c);
if(!flag)flag|=check(b,c,a);
if(!flag)flag|=check(c,a,b);
if(!flag)flag|=check(c,b,a);
if(check(x,y,z,u,v,w))printf("%d %d %d\n",x,y,z);
else if(check(x,z,y,u,v,w))printf("%d %d %d\n",x,z,y);
else if(check(y,x,z,u,v,w))printf("%d %d %d\n",y,x,z);
else if(check(y,z,x,u,v,w))printf("%d %d %d\n",y,z,x);
else if(check(z,x,y,u,v,w))printf("%d %d %d\n",z,x,y);
else if(check(z,y,x,u,v,w))printf("%d %d %d\n",z,y,x);
else printf("-1\n");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 2ms
memory: 3660kb
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 175 463 421 47 239 361 376 209 343 175 350 436 420 57 461 184 57 343 450 431 158 126 202 179 39 93 120 473 165 215 47 391 215 362 463 401 171 57 311 370 328 125 90 209 49 243 391 306 473 478 60 417 476 253 148 493 158 47 292 47 50 110 211 169 452 361 73 403 17 169 113 487 215 452 110 399 431 37 ...
result:
ok Accepted!
Test #2:
score: 10
Accepted
time: 4ms
memory: 4196kb
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:
1227 1443 324 528 898 1026 886 230 324 870 769 1000 692 1343 1533 109 461 1118 1995 506 1026 1030 1846 1672 1390 389 464 339 1819 1301 29 692 1414 836 413 471 1574 910 1050 1201 572 152 664 572 722 158 898 1845 1001 898 1227 989 1846 666 652 1950 1672 1848 1279 1220 1480 401 145 1366 436 1630 1431 2...
result:
ok Accepted!
Test #3:
score: 10
Accepted
time: 151ms
memory: 47464kb
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 143809 44962
result:
ok Accepted!
Test #4:
score: 10
Accepted
time: 151ms
memory: 47560kb
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:
174571 176688 95506
result:
ok Accepted!
Test #5:
score: 10
Accepted
time: 128ms
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:
34411 98198 27046 39355 49857 70450 52145 64637 69064 129196 118391 75453 96028 146165 32236 194867 26201 124636 193249 106205 151320 36173 44996 147780 16928 10582 147134 197158 106757 196326
result:
ok Accepted!
Test #6:
score: 10
Accepted
time: 157ms
memory: 47412kb
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 7480 3363 156481 27494 156628 134802 59297 136664 126929 139436 4472 79250 92990 19984 31684 19769 84929 77495 50600 148651 49868 10494 79717 12157 105707 36244 82672 50225 155540
result:
ok Accepted!
Test #7:
score: 10
Accepted
time: 248ms
memory: 69492kb
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:
145645 1 62949 68760 38957 1 115484 1 20705 16671 36782 1 41631 1 5656 114616 28131 1 58614 114785 1 171869 94241 1 174290 1 131964 175188 154225 1 142541 139642 1 82073 21712 1 20583 1 16556 177239 83956 1 99183 1 8150 94979 12843 1 136758 117147 1 93202 1 55604 9655 26120 1 70963 1 31750 28190 956...
result:
ok Accepted!
Test #8:
score: 10
Accepted
time: 217ms
memory: 47580kb
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:
183543 183543 178310 98115 98115 178310 36778 36778 178310 30537 30537 178310 169883 169883 178310 65826 65826 178310 31265 31265 178310 161066 161066 178310 129717 129717 178310 85 85 178310 98442 98442 178310 118809 118809 178310 183881 183881 178310 87348 87348 178310 186490 186490 178310 113946 ...
result:
ok Accepted!
Test #9:
score: 10
Accepted
time: 276ms
memory: 47392kb
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 34708 81596 66894 186401 42045 184795 95044 140544 165046 161190 15891 66610 181723 196866 119681 139020 117148 113149 177939 151070 83964 136800 199684 99848 193733 165590 75873 99034 182287 119888 44210 197331 44224 98649 113772 151223 59119 34254 3957 69646 19165 82137 122318 79516 99825 12...
result:
ok Accepted!
Test #10:
score: 10
Accepted
time: 253ms
memory: 47432kb
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 115995 19487 74523 185226 99574 113594 85322 143204 25740 146957 128773 184978 89001 83393 163893 65929 94172 130689 180089 195057 166586 159412 123029 21175 139139 181742 134043 51547 126401 3992 160570 172760 17316 110479 168064 77703 8619 156309 95660 178898 38381 55180 67418 171987 100828 ...
result:
ok Accepted!
Extra Test:
score: 0
Extra Test Passed