QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#310721 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | Harry27182 | 0 | 111ms | 26936kb | C++14 | 4.3kb | 2024-01-21 17:09:59 | 2024-01-21 17:10:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
struct edge{int v,nxt;}e[N<<1];
int cnt,h[N],f[N][20],dep[N],siz[N],son[N],dfn[N],id[N],top[N],n,m,u,v,k,tot,ans[N];
void add(int u,int v){e[++cnt]={v,h[u]};h[u]=cnt;}
void dfs(int u,int fa)
{
f[u][0]=fa;dep[u]=dep[fa]+1;siz[u]=1;
for(int i=1;(1<<i)<=n;i++)f[u][i]=f[f[u][i-1]][i-1];
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa)continue;
dfs(v,u);siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
void dfs2(int u,int tp)
{
top[u]=tp;dfn[u]=++tot;id[tot]=u;
if(son[u])dfs2(son[u],tp);
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==son[u]||v==f[u][0])continue;
dfs2(v,v);
}
}
int lca(int u,int v)
{
if(dep[u]<dep[v])swap(u,v);
for(int i=18;i>=0;i--)if(dep[f[u][i]]>=dep[v])u=f[u][i];
if(u==v)return u;
for(int i=18;i>=0;i--)if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
return f[u][0];
}
struct node{int d,w,id;};
namespace Part1
{
vector<node>qh[N],ql[N];int numl[N],numh[N],sum;
void insert(int u,int v,int k,int id)
{
ans[id]+=dep[u]-dep[v]+1;
if(son[u])qh[son[u]].emplace_back(node{min(dep[u]+k,n),1,id});
ql[u].emplace_back(node{k,1,id});ql[f[v][0]].emplace_back(node{k,-1,id});
while(top[u]!=top[v])
{
qh[top[u]].emplace_back(node{min(dep[f[top[u]][0]]+k,n),-1,id});
qh[son[f[top[u]][0]]].emplace_back(node{min(dep[f[top[u]][0]]+k,n),1,id});
u=f[top[u]][0];
}
}
void dfs(int u,int fa)
{
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa||v==son[u])continue;
for(int j=dfn[v];j<dfn[v]+siz[v];j++)
{
int x=id[j];
numl[dep[x]-dep[u]]+=siz[x];sum++;
}
}
for(int i=0;i<ql[u].size();i++)ans[ql[u][i].id]+=ql[u][i].w*(sum-numl[ql[u][i].d+1]);
for(int i=0;i<qh[u].size();i++)ans[qh[u][i].id]+=qh[u][i].w*numh[qh[u][i].d+1];
numh[dep[u]]+=siz[u];
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa)continue;
dfs(v,u);
}
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa||v==son[u])continue;
for(int j=dfn[v];j<dfn[v]+siz[v];j++)
{
int x=id[j];
numl[dep[x]-dep[u]]-=siz[x];sum--;
}
}
for(int i=0;i<qh[u].size();i++)ans[qh[u][i].id]+=qh[u][i].w*(siz[u]-numh[qh[u][i].d+1]);
}
void main()
{
dfs(1,0);
}
}
namespace Part2
{
int siz[N],mx[N],vis[N],S,rt,val[N],mxd,sum[N];vector<pair<int,int> >q[N];
void find(int u,int fa)
{
siz[u]=1;mx[u]=0;
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa||vis[v])continue;
find(v,u);mx[u]=max(mx[u],siz[v]);
siz[u]+=siz[v];
}
mx[u]=max(mx[u],S-siz[u]);
if(mx[u]<mx[rt])rt=u;
}
int get(int u,int fa)
{
int res=1;
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa||vis[v])continue;
res+=get(v,u);
}
return res;
}
void dfs(int u,int fa,int w,int d)
{
val[d]+=w;mxd=max(mxd,d);
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa||vis[v])continue;
dfs(v,u,w,d+1);
}
}
void dfs2(int u,int fa,int d)
{
for(int i=0;i<q[u].size();i++)if(q[u][i].first>=d)ans[q[u][i].second]+=sum[min(mxd,q[u][i].first-d)];
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa)continue;
dfs2(v,u,d+1);
}
}
void solve(int u)
{
vis[u]=1;mxd=0;
dfs(u,0,1,0);
for(int i=0;i<=mxd;i++)sum[i]=val[i];
for(int i=1;i<=mxd;i++)sum[i]+=sum[i-1];
for(int i=0;i<q[u].size();i++)ans[q[u][i].second]+=sum[q[u][i].first];
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(vis[v])continue;
dfs(v,u,-1,1);
for(int j=0;j<=mxd;j++)sum[j]=val[j];
for(int j=1;j<=mxd;j++)sum[j]+=sum[j-1];
dfs2(v,u,1);dfs(v,u,1,1);
}
dfs(u,0,-1,0);
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(vis[v])continue;
mx[rt=0]=0x3f3f3f3f;S=get(v,u);find(v,u);solve(rt);
}
}
void main()
{
mx[rt=0]=0x3f3f3f3f;S=n;find(1,0);solve(rt);
}
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin>>n;
for(int i=1;i<n;i++)
{
cin>>u>>v;
add(u,v);add(v,u);
}
dfs(1,0);dfs2(1,1);
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>u>>v>>k;
int Lca=lca(u,v);
Part1::insert(u,Lca,k,i);Part1::insert(v,Lca,k,i);
Part1::qh[Lca].emplace_back(node{min(dep[Lca]+k,n),-2,i});
Part2::q[Lca].emplace_back(make_pair(k,i));
}
Part1::main();Part2::main();
for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
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: 111ms
memory: 26936kb
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:
7102 3040 15997 216 257 9840 9756 3025 15945 4301 316 467 14001 320 15823 15997 15945 2952 15990 12 2868 15010 15945 14556 19 82 15829 13913 216 15393 549 9563 1150 2892 221 7270 1545 339 84 15007 7210 70 81 12277 15829 744 15051 15945 113 566 75 171 217 3171 15990 10013 100 7044 237 66 15387 601 15...
result:
wrong answer 1st numbers differ - expected: '3226', found: '7102'
Subtask #2:
score: 0
Time Limit Exceeded
Test #9:
score: 0
Time Limit Exceeded
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:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Time Limit Exceeded
Test #25:
score: 0
Time Limit Exceeded
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:
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%