QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#90584 | #5828. 游戏 | Kanate | 20 | 633ms | 60356kb | C++14 | 4.3kb | 2023-03-23 20:13:14 | 2023-03-23 20:13:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define rint int
#define endl '\n'
int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)) x=x*10+c-48,c=getchar();
return x*f;
}const int N=2e5+10,p=1e9;
int n,m;
vector<int> e[N];
struct Val{
int x,id;
bool operator <(const Val &A)const{return x>A.x;}
};
struct data{
Val x,y,z;
void operator+=(const Val &A)
{
if(A<x) z=y,y=x,x=A;
else if(A<y) z=y,y=A;
else if(A<z) z=A;
}
}d[N];
void dfs(int x=1,int fa=1)
{
d[x]={0,x,-p,0,-p,0};
for(auto &it:e[x])
if(it!=fa)
{
dfs(it,x);
Val res=d[it].x;
res.x++,d[x]+=res;
}
}
Val sum[N],suf[N];
void sel(int x=1,int fa=1,Val res={-p,0})
{
res.x++,d[x]+=res;
int sz=e[x].size();Val tmp;
for(rint i=0;i<sz;i++) tmp=d[e[x][i]].x,tmp.x++,sum[e[x][i]]=suf[e[x][i]]=(e[x][i]==fa?res:min(tmp,res));
for(rint i=1;i<sz;i++) sum[e[x][i]]=min(sum[e[x][i]],sum[e[x][i-1]]);
for(rint i=sz-2;~i;i--) suf[e[x][i]]=min(suf[e[x][i]],suf[e[x][i+1]]);
if(sz==1) return;
if(e[x][0]!=fa) sel(e[x][0],x,suf[e[x][1]]);
if(e[x][sz-1]!=fa) sel(e[x][sz-1],x,sum[e[x][sz-2]]);
for(rint i=1;i+1<sz;i++)
if(e[x][i]!=fa) sel(e[x][i],x,min(sum[e[x][i-1]],suf[e[x][i+1]]));
}
int mm;
struct node{
int x,y,z,id;bool how;
}q[N];
struct cmp{
bool operator ()(const node &A,const node &B){return A.z<B.z;}
};
bool cmpx(const node &A,const node &B){return A.x!=B.x?A.x<B.x:A.how>B.how;}
bool cmpy(const node &A,const node &B){return A.y!=B.y?A.y<B.y:A.how>B.how;}
multiset<node,cmp> s;
vector<node> ve[N];
bool use[N];
void cdq(int l=1,int r=mm)
{
if(l==r) return;
int mid=(l+r)>>1;
cdq(l,mid);
sort(q+l,q+mid+1,cmpy),sort(q+mid+1,q+r+1,cmpy);
for(rint i=l,j=mid+1;j<=r;j++)
{
while(i<=mid&&q[i].y<=q[j].y){
if(q[i].how&&!use[q[i].id]) s.insert(q[i]);
i++;
}
if(!q[j].how)
{
auto it=s.upper_bound(q[j]);
while(it!=s.begin())
{
--it;
ve[q[j].id].push_back(*it),use[it->id]=1;
it=s.erase(it);
}
}
}
s.clear();
cdq(mid+1,r);
}
void init()
{
dfs(),sel();
// for(rint i=1;i<=n;i++)
// cout<<i<<":("<<d[i].x.x<<" "<<d[i].x.id<<") "
// <<"("<<d[i].y.x<<" "<<d[i].y.id<<") "
// <<"("<<d[i].z.x<<" "<<d[i].z.id<<")"<<endl;
mm=m;
for(rint i=1;i<=n;i++) q[++mm]={d[i].x.x,d[i].y.x,d[i].z.x,i,0};
cdq();
// for(rint i=1;i<=n;i++)
// {
// cout<<i<<": ";
// for(auto &it:ve[i]) cout<<it.id<<" ";cout<<endl;
// }
}
int FA[N],D[N],sz[N],son[N];
int dfn[N],tot,top[N],o[N];
void dfs1(int x=1,int fa=0,int dep=1)
{
FA[x]=fa,D[x]=dep,sz[x]=1;
for(auto &it:e[x])
if(it!=fa)
{
dfs1(it,x,dep+1),sz[x]+=sz[it];
if(sz[son[x]]<sz[it]) son[x]=it;
}
}
void dfs2(int x=1,int tp=1)
{
dfn[x]=++tot,top[x]=tp,o[tot]=x;
if(!son[x]) return;
dfs2(son[x],tp);
for(auto &it:e[x])
if(!dfn[it]) dfs2(it,it);
}
int ask(int l,int r,int dep)
{
int x=l,y=r,fa;
while(top[x]!=top[y])
{
if(D[top[x]]<D[top[y]]) swap(x,y);
x=FA[top[x]];
}
if(D[x]>D[y]) fa=y;
else fa=x;
// cout<<"ask "<<l<<" "<<r<<" "<<fa<<" "<<dep<<endl;
if(D[l]-dep>=D[fa])
{
int tar=D[l]-dep;
while(D[top[l]]>tar) l=FA[top[l]];
return o[dfn[l]-(D[l]-tar)];
}
else
{
int tar=D[fa]+dep-(D[l]-D[fa]);
while(D[top[r]]>tar) r=FA[top[r]];
return o[dfn[r]-(D[r]-tar)];
}
}
int ans[N][3],ord[N][3];
void work()
{
dfs1(),dfs2();
for(rint i=1;i<=n;i++)
for(auto &it:ve[i])
ans[it.id][ord[it.id][0]]=ask(i,d[i].x.id,it.x),
ans[it.id][ord[it.id][1]]=ask(i,d[i].y.id,it.y),
ans[it.id][ord[it.id][2]]=ask(i,d[i].z.id,it.z);
for(rint i=1;i<=m;i++) cout<<ans[i][0]<<" "<<ans[i][1]<<" "<<ans[i][2]<<endl;
}
signed main()
{
// ios::sync_with_stdio(0);
n=read();
for(rint i=1;i<n;i++)
{
int x=read(),y=read();
e[x].push_back(y),e[y].push_back(x);
}
m=read();
for(rint i=1;i<=m;i++)
{
int x=read(),z=read(),y=read();
q[i]={(x-y+z)>>1,(x+y-z)>>1,(y+z-x)>>1,i,1},ord[i][1]=1,ord[i][2]=2;
if(q[i].y>q[i].x) swap(q[i].y,q[i].x),swap(ord[i][0],ord[i][1]);
if(q[i].z>q[i].y) swap(q[i].z,q[i].y),swap(ord[i][1],ord[i][2]);
if(q[i].y>q[i].x) swap(q[i].y,q[i].x),swap(ord[i][0],ord[i][1]);
// cout<<"q "<<i<<" "<<q[i].x<<" "<<q[i].y<<" "<<q[i].z<<endl;
}
init();
work();
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 12864kb
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:
344 21 37 312 488 386 125 362 21 193 215 149 297 386 330 26 280 165 193 28 486 261 283 360 399 268 30 151 60 87 152 360 427 183 74 270 124 265 227 124 342 399 146 17 21 360 477 427 477 60 331 60 417 266 74 323 39 17 360 219 26 281 438 10 298 331 68 399 332 205 416 50 152 152 331 51 270 356 37 172 18...
result:
wrong answer Wrong answer on test 2
Test #2:
score: 0
Wrong Answer
time: 7ms
memory: 13216kb
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:
1449 1560 441 0 0 0 679 650 275 1381 1941 1955 861 266 546 234 1937 926 0 0 0 731 552 87 215 1672 891 1546 798 396 1215 861 1596 1671 1756 1143 1060 589 134 182 422 822 1050 422 725 895 546 605 822 546 266 1981 552 951 0 0 0 0 0 0 266 1772 1272 504 243 1050 0 0 0 1726 1795 646 323 1557 27 1764 303 1...
result:
wrong answer Wrong answer on test 1
Test #3:
score: 0
Wrong Answer
time: 261ms
memory: 36592kb
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:
44708 71361 45838
result:
wrong answer Wrong answer on test 1
Test #4:
score: 10
Accepted
time: 256ms
memory: 36668kb
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:
154818 24899 74592
result:
ok Accepted!
Test #5:
score: 0
Wrong Answer
time: 262ms
memory: 36584kb
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:
137496 1448 35530 144255 137984 179117 53739 89886 119043 141295 148920 90290 103697 156208 171061 29198 153727 22907 112619 40968 68885 23757 12553 141497 22362 93534 21452 1480 129015 63023
result:
wrong answer Wrong answer on test 1
Test #6:
score: 10
Accepted
time: 232ms
memory: 36548kb
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:
41374 151532 107872 59536 166333 11082 191314 176954 147915 53508 78768 7072 48857 25606 197721 164631 28349 60403 110232 16163 3 117163 99474 92047 188690 169825 168093 113102 46567 63864
result:
ok Accepted!
Test #7:
score: 0
Wrong Answer
time: 354ms
memory: 60356kb
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:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer Integer 0 violates the range [1, 200000]
Test #8:
score: 0
Wrong Answer
time: 522ms
memory: 53860kb
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:
167604 167604 181947 167604 167604 126248 167604 167604 116508 167604 167604 77572 167604 167604 189796 167604 167604 32539 167604 167604 31161 167604 167604 88736 167604 167604 189194 167604 167604 199382 167604 167604 95130 167604 167604 99255 167604 167604 129420 167604 167604 139777 167604 16760...
result:
wrong answer Wrong answer on test 28
Test #9:
score: 0
Wrong Answer
time: 633ms
memory: 47704kb
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:
7107 27232 141796 199425 90489 109653 35744 50284 59455 50102 130361 28875 181116 33135 161848 169934 88637 85106 129492 130795 76945 186265 65710 90715 144848 64937 105187 23869 155062 124671 84782 35817 167918 43450 7480 46422 82742 193611 102475 92303 150834 38338 75275 167560 10364 137993 25195 ...
result:
wrong answer Wrong answer on test 2
Test #10:
score: 0
Wrong Answer
time: 627ms
memory: 47744kb
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:
135279 172309 26462 187823 115844 191502 81355 142861 77153 94624 51830 167769 176965 88035 170884 185194 11608 64977 115054 5331 76357 16214 101600 118957 141386 35201 113627 26107 101442 89477 132582 100122 165252 98743 145411 111633 74622 10772 21901 74198 83219 175428 33976 26061 63251 50049 621...
result:
wrong answer Wrong answer on test 3