QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#410102 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | grass8cow | 0 | 718ms | 135828kb | C++17 | 4.5kb | 2024-05-13 12:50:33 | 2024-05-13 12:50:34 |
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;
sz[x]+=sz[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: 43040kb
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:
371 60 2856 98 12 611 611 106 3397 361 76 61 1124 -12 3371 2877 4100 219 4197 4 189 1030 4083 4032 5 11 1730 723 -10 2017 132 923 116 161 5 680 -96 76 28 1769 493 2 45 513 2341 144 1823 2330 9 -91 30 14 27 197 4522 555 21 64 -7 7 3980 5 4516 28 2172 278 5 2593 10 1575 372 27 877 -116 -23 2183 157 21...
result:
wrong answer 1st numbers differ - expected: '3226', found: '371'
Subtask #2:
score: 0
Runtime Error
Test #9:
score: 8
Accepted
time: 622ms
memory: 106996kb
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: 617ms
memory: 135828kb
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: 718ms
memory: 91156kb
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: 694ms
memory: 105280kb
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:
21 16469 63960 1949 7706 124400 1917 21763 36 1283 -9 11 214 140956 3 26334 20 87750 114381 4019 3334 62609 23 9559 2440 245 98852 26612 362 -12 137081 -123 32 66988 273 -3354 25433 170026 89 28878 28794 95663 1998 6657 10178 57319 9549 251 27 578 8194 12015 648 85899 154255 319 15733 13714 16 79968...
result:
wrong answer 1st numbers differ - expected: '78', found: '21'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%