QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#310725 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | Harry27182 | 0 | 703ms | 120184kb | C++14 | 4.4kb | 2024-01-21 17:13:32 | 2024-01-21 17:13:36 |
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||vis[v])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: 16ms
memory: 27540kb
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:
3226 2028 4988 208 252 3970 3886 2013 4974 2118 308 391 4768 312 4954 4988 4974 1551 4981 12 1856 4825 4974 3585 19 82 4960 4680 208 4870 474 3693 808 1880 213 3394 1203 266 84 4822 3334 70 81 4501 4960 668 4866 4974 113 490 75 163 209 2159 4981 4143 100 3168 232 66 4864 525 4958 390 4713 2305 15 35...
result:
wrong answer 24th numbers differ - expected: '4974', found: '3585'
Subtask #2:
score: 0
Wrong Answer
Test #9:
score: 0
Wrong Answer
time: 529ms
memory: 71940kb
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:
1193 104153 9170 249115 159552 221 35704 199179 7224 17078 30146 119050 560 777 23 11778 89 71317 213653 109 49747 193400 98540 5148 1471 68 66375 62281 199860 292121 93110 398 1 24 6 4 3 14 61421 199859 199152 259687 196278 260439 55552 56091 179198 931 196281 199988 5352 112 102787 142067 198158 2...
result:
wrong answer 1st numbers differ - expected: '757', found: '1193'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 703ms
memory: 120184kb
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:
78 107329 190250 5672 110415 199160 3826 96672 75 13429 149 58 704 199639 25 190454 489 198350 197627 10273 172193 192719 99 191654 80328 481 195140 172164 120515 290 199616 719 142 195166 2607 20737 135444 199768 2433 164666 180527 198261 14511 53672 69060 185790 110874 639 131 2130 188357 150164 2...
result:
wrong answer 28th numbers differ - expected: '170809', found: '172164'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%