QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#88918 | #5828. 游戏 | Larunatrecy | 10 | 278ms | 69500kb | C++14 | 3.5kb | 2023-03-17 22:16:59 | 2023-03-17 22:17:00 |
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(y,z)!=v)return 0;
if(tree::dist(z,x)!=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: 0
Wrong Answer
time: 1ms
memory: 3872kb
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:
175 421 463 47 421 239 376 361 209 175 343 350 420 436 57 184 461 57 450 343 431 126 158 202 39 179 93 473 120 165 47 215 391 362 215 463 171 401 57 370 311 328 90 125 209 243 49 391 473 306 478 417 60 476 148 253 493 47 158 292 50 47 110 169 211 452 73 361 403 169 17 113 487 215 452 399 110 431 116...
result:
wrong answer Wrong answer on test 1
Test #2:
score: 0
Wrong Answer
time: 4ms
memory: 4224kb
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:
1443 1227 324 898 528 1026 230 886 324 769 870 1000 1343 692 1533 461 109 1118 506 1995 1026 1846 1030 1672 389 1390 464 1819 339 1301 692 29 1414 413 836 471 910 1574 1050 572 1201 152 572 664 722 898 158 1845 898 1001 1227 1846 989 666 1950 652 1672 1279 1848 1220 401 1480 145 436 1366 1630 278 14...
result:
wrong answer Wrong answer on test 1
Test #3:
score: 0
Wrong Answer
time: 143ms
memory: 47468kb
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:
143809 87763 44962
result:
wrong answer Wrong answer on test 1
Test #4:
score: 0
Wrong Answer
time: 170ms
memory: 47460kb
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:
176688 174571 95506
result:
wrong answer Wrong answer on test 1
Test #5:
score: 0
Wrong Answer
time: 151ms
memory: 47608kb
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:
98198 34411 27046 49857 39355 70450 64637 52145 69064 118391 129196 75453 146165 96028 32236 26201 194867 124636 106205 193249 151320 44996 36173 147780 10582 16928 147134 106757 197158 196326
result:
wrong answer Wrong answer on test 1
Test #6:
score: 0
Wrong Answer
time: 142ms
memory: 47596kb
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:
7480 145500 3363 27494 156481 156628 59297 134802 136664 139436 126929 4472 92990 79250 19984 19769 31684 84929 50600 77495 148651 10494 49868 79717 105707 12157 36244 50225 82672 155540
result:
wrong answer Wrong answer on test 1
Test #7:
score: 0
Wrong Answer
time: 253ms
memory: 69500kb
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:
1 145645 62949 38957 68760 1 1 115484 20705 36782 16671 1 1 41631 5656 28131 114616 1 114785 58614 1 94241 171869 1 1 174290 131964 154225 175188 1 139642 142541 1 21712 82073 1 1 20583 16556 83956 177239 1 1 99183 8150 12843 94979 1 117147 136758 1 1 93202 55604 26120 9655 1 1 70963 31750 95600 281...
result:
wrong answer Wrong answer on test 1
Test #8:
score: 10
Accepted
time: 236ms
memory: 47620kb
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: 0
Wrong Answer
time: 276ms
memory: 47456kb
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:
34708 80097 81596 186401 66894 42045 95044 184795 140544 161190 165046 15891 181723 66610 196866 139020 119681 117148 177939 113149 151070 136800 83964 199684 193733 99848 165590 99034 75873 182287 44210 119888 197331 98649 44224 113772 59119 151223 34254 69646 3957 19165 122318 82137 79516 120870 9...
result:
wrong answer Wrong answer on test 1
Test #10:
score: 0
Wrong Answer
time: 278ms
memory: 47464kb
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:
115995 46612 19487 185226 74523 99574 85322 113594 143204 146957 25740 128773 89001 184978 83393 65929 163893 94172 180089 130689 195057 159412 166586 123029 139139 21175 181742 51547 134043 126401 160570 3992 172760 110479 17316 168064 8619 77703 156309 178898 95660 38381 67418 55180 171987 184141 ...
result:
wrong answer Wrong answer on test 1