QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#410099 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | grass8cow | 0 | 563ms | 137560kb | C++17 | 4.5kb | 2024-05-13 12:48:14 | 2024-05-13 12:48:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n;
#define pb push_back
const int N=2e5+10;
vector<int>g[N];
namespace Dia{
bool vis[N];
int di[25][N],F[N],dk[N];
int ae[N*25];
int al[N],ar[N],bl[N],br[N],cn;
int sz[N],rt,Mx,S;
void df(int x,int f){
sz[x]=1;int mm=-1;
for(int v:g[x])
if(v!=f&&!vis[v])df(v,x),mm=max(mm,sz[v]),sz[x]+=sz[v];
mm=max(mm,S-sz[x]);if(mm<Mx)Mx=mm,rt=x;
}
int T1[N],T2[N],md1,md2;
int O,oe;
void dfs2(int x,int d,int f){
oe++;
di[O][x]=d;
while(md1<d)md1++,T1[md1]=0;
while(md2<d)md2++,T2[md2]=0;
T1[d]++,T2[d]++;
for(int v:g[x])
if(v!=f&&!vis[v])dfs2(v,d+1,x),sz[x]+=sz[v];
}
int fz[N];
void sol(int x){
vis[x]=1,O=dk[x];
T1[0]=(x<=n),md1=0;
for(int v:g[x])if(!vis[v]){
T2[0]=0,md2=0;
oe=0,dfs2(v,1,0);
for(int i=1;i<=md2;i++)T2[i]+=T2[i-1];
S=oe,Mx=S+1,df(v,0);
F[rt]=x,dk[rt]=dk[x]+1,fz[v]=rt;
bl[rt]=cn+1,br[rt]=cn+md2+1;
for(int i=0;i<=md2;i++)ae[++cn]=T2[i];
}
for(int i=1;i<=md1;i++)T1[i]+=T1[i-1];
al[x]=cn+1,ar[x]=cn+md1+1;
for(int i=0;i<=md1;i++)ae[++cn]=T1[i];
for(int v:g[x])if(!vis[v])sol(fz[v]);
}
int oi[N],fp[N];
int Ask(int x,int d){
if(d<0)return 0;
int u=x,su=0,nx=0;
while(u){
int oi=di[dk[u]][x];
if(oi<=d){
su+=ae[min(ar[u],al[u]+d-oi)];
if(nx)su-=ae[min(br[nx],bl[nx]+d-oi)];
}
nx=u,u=F[u];
}
return su;
}
void build(){
oe=cn=0;
for(int i=1;i<=n;i++)T1[i]=T2[i]=oi[i]=fp[i]=dk[i]=ae[i]=al[i]=ar[i]=bl[i]=br[i]=F[i]=dk[i]=0,vis[i]=0;
S=n,Mx=n+1,df(1,0),sol(rt);
}
}
int sz[201000],son[201000],dfn[201000],top[200100],db[200100],bel[200100],fa[201000],d[201000];
void dfs(int x){
sz[x]=1;int mm=-1;
for(int v:g[x])if(v!=fa[x]){
fa[v]=x,d[v]=d[x]+1,dfs(v);
if(mm<sz[v])mm=sz[v],son[x]=v;
}
}
void dfs2(int x,int ff){
bel[dfn[x]=++dfn[0]]=x,top[x]=ff;
if(!son[x]){db[x]=x;return;}
dfs2(son[x],ff),db[x]=db[son[x]];
for(int v:g[x])if(v!=fa[x]&&v!=son[x])dfs2(v,v);
}
int lca(int u,int v){
if(top[u]!=top[v]){
if(d[top[u]]<d[top[v]])swap(u,v);
u=fa[top[u]];
}
if(d[u]>d[v])swap(u,v);return u;
}
struct BIT{
int tr[201000];
bool vis[201000];
int sta[200100],top;
inline void ad(int x,int z){
for(x++;x<=n+1;x+=(x&-x)){
if(!vis[x])vis[x]=1,sta[++top]=x;
tr[x]+=z;
}
}
inline int ask(int x){
if(x<0)return 0;
x=min(x,n);
int s=0;
for(x++;x;x-=(x&-x))s+=tr[x];
return s;
}
inline void cl(){
while(top)vis[sta[top]]=0,tr[sta[top]]=0,top--;
}
}T;
int ans[200100];
vector<array<int,3> >G[200100];
void sg(int u,int d,int id,int z){
while(u)
G[u].pb({d,id,z}),u=fa[top[u]];
}
void sol(){
scanf("%d",&n);
for(int i=1;i<=n;i++)g[i].clear(),sz[i]=son[i]=dfn[i]=top[i]=db[i]=bel[i]=fa[i]=d[i]=0,G[i].clear();
for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),g[u].pb(v),g[v].pb(u);
Dia::build();
dfn[0]=0,dfs(1),dfs2(1,1);
int q;
scanf("%d",&q);
for(int i=1,u,v,d;i<=q;i++){
scanf("%d%d%d",&u,&v,&d);
int lc=lca(u,v);
ans[i]=Dia::Ask(lc,d);
sg(u,d,i,1),sg(v,d,i,1),sg(lc,d,i,-2);
}
for(int t=1;t<=n;t++)if(top[t]==t){
for(int j=dfn[t];j<=dfn[db[t]];j++){
int u=bel[j];
T.ad(0,1),T.ad(d[u]-d[t]+1,-1);
if(son[u]){
for(int k=dfn[son[u]]+sz[son[u]];k<dfn[u]+sz[u];k++){
int z=d[bel[k]]-d[u];
T.ad(z,1),T.ad(z+1+(d[u]-d[t]),-1);
}
}
for(auto it:G[u])ans[it[1]]+=T.ask(it[0])*it[2];
}
T.cl();
for(int j=dfn[db[t]];j>dfn[t];j--){
int u=bel[j];
T.ad(d[u]-d[t],1);
if(son[u]){for(int k=dfn[son[u]]+sz[son[u]];k<dfn[u]+sz[u];k++)T.ad(d[bel[k]]-d[t],1);}
for(auto it:G[fa[u]])
ans[it[1]]+=(T.ask(it[0]+(d[u]-d[t]-1))-T.ask(it[0]-1))*it[2];
}
T.cl();
}
for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
}
int main(){
int T=1;while(T--)sol();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 7ms
memory: 43192kb
input:
4988 1 2 1 3 1 4 4 5 1 6 3 7 3 8 5 9 4 10 6 11 3 12 9 13 11 14 8 15 11 16 1 17 7 18 8 19 18 20 7 21 10 22 15 23 18 24 4 25 24 26 9 27 23 28 3 29 3 30 30 31 11 32 18 33 2 34 32 35 29 36 29 37 19 38 9 39 6 40 25 41 16 42 31 43 6 44 42 45 32 46 27 47 32 48 44 49 7 50 10 51 24 52 46 53 30 54 46 55 39 56...
output:
619 57 2849 30 11 119 94 48 3397 119 15 92 1183 17 3369 3593 3515 115 4197 4 172 1069 4083 4032 3 10 1573 694 8 1306 24 791 164 76 18 467 22 51 11 1727 111 6 11 206 2655 31 1737 2330 6 31 7 19 13 11 4197 236 6 327 9 14 3980 12 4100 13 2058 430 3 2593 8 1620 504 11 487 29 14 1209 141 2182 4618 2478 2...
result:
wrong answer 1st numbers differ - expected: '3226', found: '619'
Subtask #2:
score: 0
Runtime Error
Test #9:
score: 8
Accepted
time: 491ms
memory: 114424kb
input:
199995 1 2 2 3 2 4 1 5 3 6 5 7 6 8 4 9 2 10 5 11 5 12 1 13 1 14 1 15 13 16 1 17 10 18 16 19 11 20 8 21 17 22 4 23 19 24 7 25 22 26 8 27 14 28 1 29 9 30 3 31 3 32 21 33 19 34 26 35 34 36 5 37 29 38 22 39 5 40 13 41 28 42 8 43 35 44 22 45 14 46 12 47 32 48 11 49 8 50 18 51 23 52 18 53 4 54 6 55 10 56 ...
output:
757 69428 2793 181264 91707 182 32496 199183 6399 15975 11640 119051 236 689 15 9532 41 36592 178936 56 45424 193403 90248 3417 949 68 34133 60471 199861 188090 75088 127 1 6 4 3 3 11 61157 199860 199153 155706 196287 192862 53742 51862 179199 428 196282 199989 3613 26 99007 134461 198159 20382 7518...
result:
ok 199996 numbers
Test #10:
score: 8
Accepted
time: 456ms
memory: 137560kb
input:
199993 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54 2...
output:
22 31743 62 30 510 6079 94 24063 190 4079 382 30 62 12159 1022 2043 8063 62 4 3063 4079 30 254 46 10 22 6111 12159 16127 22 1 12031 1 94 382 766 4063 254 46 766 1022 62 766 1 22 46 30 8063 8063 254 3063 22 62 30 1 62 254 4 10 15871 1022 46 2039 6079 22 254 1022 16127 30 766 8127 14 14 10 46 1 62 406...
result:
ok 199995 numbers
Test #11:
score: 8
Accepted
time: 563ms
memory: 91416kb
input:
199993 25163 125238 125238 19096 19096 88864 88864 113505 113505 12722 12722 56225 56225 8736 8736 74926 74926 38529 38529 80231 80231 19719 19719 198784 198784 75213 75213 190174 190174 163340 163340 62363 62363 144160 144160 130912 130912 3919 3919 21218 21218 85281 85281 187312 187312 79930 79930...
output:
97095 57496 116181 132482 144412 69917 174677 96334 37980 80902 148979 22074 166530 153392 43419 163281 148526 62703 79363 199993 153733 152298 5085 156125 117973 61925 36346 95741 124148 102890 20093 5408 77598 176994 177809 169850 144418 43786 189237 69098 5167 199993 103575 105198 197612 38829 20...
result:
ok 199994 numbers
Test #12:
score: 0
Runtime Error
input:
200000 3219 118490 118490 61372 61372 74390 74390 88375 88375 63918 63918 37580 37580 33219 33219 170480 170480 81737 81737 153202 153202 93921 93921 149109 149109 88339 88339 167037 167037 67099 67099 58363 58363 6784 6784 109386 109386 11895 11895 14872 14872 65638 65638 43958 43958 181669 181669 ...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 542ms
memory: 113992kb
input:
199991 1 2 2 3 3 4 3 5 5 6 3 7 1 8 8 9 8 10 10 11 1 12 1 13 13 14 4 15 12 16 13 17 17 18 8 19 3 20 9 21 16 22 10 23 1 24 7 25 6 26 12 27 4 28 21 29 27 30 30 31 21 32 19 33 20 34 17 35 7 36 13 37 24 38 37 39 30 40 31 41 15 42 9 43 32 44 41 45 18 46 38 47 8 48 35 49 13 50 35 51 47 52 35 53 48 54 44 55...
output:
8 20452 63744 32 624 124364 54 13274 8 77 13 7 15 140913 3 12418 10 88231 114283 106 4014 70020 4 8380 744 11 98871 30889 962 33 91478 24 8 66981 12 53 14258 155478 25 29850 22798 95065 247 470 190 34304 1657 16 12 18 5061 1645 642 84225 154366 39 552 2994 11 80180 16468 356 11469 144290 76357 20639...
result:
wrong answer 1st numbers differ - expected: '78', found: '8'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%