QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#702612 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | FLY | 0 | 883ms | 180020kb | C++14 | 5.4kb | 2024-11-02 16:16:58 | 2024-11-02 16:16:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define gc getchar
#define pb push_back
#define abs_(x) max(x,-(x))
#define tomin(x,y) x=min(x,y)
#define tomax(x,y) x=max(x,y)
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define dFor(i,a,b) for(int i=(a);i>=(b);i--)
#define all(x) x.begin(),x.end()
const int N=2e5+5;
int read()
{
int x=0; int y=1; char c=gc();
for(;!isdigit(c);c=getchar()) if(c=='-') y=0;
for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
return y?x:-x;
}
int n,Q;
vector<int> e[N];
int ans[N];
int fa[N],d[N],sz[N],son[N],dfn[N],idfn[N],ed[N],dct,top[N];
int bz[20][N],lg[N];
void dfs0(int u)
{
d[u]=d[fa[u]]+1;
sz[u]=1;
son[u]=0;
for(int v:e[u]) if(v^fa[u])
{
fa[v]=u;
dfs0(v);
sz[u]+=sz[v];
if(sz[v]>sz[son[u]]) son[u]=v;
}
}
void dfs1(int u,int tp)
{
top[u]=tp;
dfn[u]=++dct;
idfn[dfn[u]]=u;
bz[0][dct]=dfn[fa[u]];
if(son[u]) dfs1(son[u],tp);
for(int v:e[u]) if((v^fa[u])&&(v^son[u]))
{
dfs1(v,v);
}
ed[u]=dct;
}
int get_mn(int l,int r)
{
int t=lg[r-l+1];
return min(bz[t][l],bz[t][r-(1<<t)+1]);
}
int lca(int u,int v)
{
if(u==v) return u;
u=dfn[u],v=dfn[v];
if(u>v) swap(u,v);
return idfn[get_mn(u+1,v)];
}
int dis(int u,int v)
{
return d[u]+d[v]-2*d[lca(u,v)];
}
int Fa[N],Sz[N],Rt,n2;
bool vs[N];
vector<int> d1[N],d2[N];
int tsz[N],mx[N];
void dfs2(vector<int> &x,int u,int fa,int s)
{
// cout<<u<<" ";
// cout<<" "<<s<<" "<<u<<endl;
// cout<<u<<endl;
x[dis(u,s)]++;
for(int v:e[u]) if((v^fa)&&!vs[v]) dfs2(x,v,u,s);
}
int get_sz(int u,int fa)
{
// cout<<u<<endl;
int s=1;
for(int v:e[u]) if((v^fa)&&!vs[v]) s+=get_sz(v,u);
return s;
}
void get_rt(int u,int fa)
{
// cout<<u<<endl;
tsz[u]=1; mx[u]=0;
for(int v:e[u]) if((v^fa)&&!vs[v])
{
get_rt(v,u);
tsz[u]+=tsz[v];
tomax(mx[u],tsz[v]);
}
tomax(mx[u],n2-tsz[u]);
if(mx[u]*2<=n2) Rt=u;
}
void Divide(int u)
{
// cout<<u<<endl;
vs[u]=1;
d1[u].resize(Sz[u]+3,0);
d2[u].resize(Sz[u]+3,0);
dfs2(d1[u],u,0,u);
// puts("");
if(u^1) dfs2(d2[u],u,0,Fa[u]);
// puts("");
for(int i=1;i<d1[u].size();i++) d1[u][i]+=d1[u][i-1];
for(int i=1;i<d2[u].size();i++) d2[u][i]+=d2[u][i-1];
// for(int i=0;i<d1[u].size();i++) cout<<d2[u][i]<<" ";
// puts("");
// puts("");
for(int v:e[u]) if(!vs[v])
{
n2=get_sz(v,u);
get_rt(v,u);
Fa[Rt]=u;
Sz[Rt]=n2;
Divide(Rt);
}
}
int query1(int u,int d)
{
int s=0;
for(int v=u;v;v=Fa[v])
{
int t=dis(v,u);
if(t<=d)
{
s+=d1[v][d-t];
// cout<<u<<" "<<v<<" "<<d<<" "<<t<<" "<<d1[v][d-t]<<","<<d2[v][d-t]<<endl;
if(v!=1&&dis(v,Fa[v])<=d) s-=d2[v][d-dis(v,Fa[v])];
}
}
return s;
}
void pre1()
{
For(i,2,n) lg[i]=lg[i>>1]+1;
dfs0(1);
dfs1(1,1);
For(i,1,lg[n])
{
For(j,1,n-(1<<i)+1) bz[i][j]=min(bz[i-1][j],bz[i-1][j+(1<<i-1)]);
}
Sz[1]=n;
Divide(1);
// For(i,1,n)
// {
// For(j,1,n) cout<<dis(i,j)<<" ";
// puts("");
// }
}
struct _N
{
int id,d,x;
};
vector<_N> g1[N],g2[N];
void solve(int id,int u,int d,int x)
{
g1[u].pb((_N){id,d,x});
if(d)
{
g2[son[u]].pb((_N){id,d-1,x});
for(int v=top[u];v^1;v=top[fa[v]])
{
g2[v].pb((_N){id,d-1,-x});
g2[son[fa[v]]].pb((_N){id,d-1,x});
}
}
}
namespace B
{
int c[N];
void cls() { memset(c,0,sizeof(c)); }
#define lb(x) x&-x
void add(int x,int y)
{
x++;
for(int i=x;i<=n;i+=lb(i)) c[i]+=y;
}
void cls(int x)
{
x++;
for(int i=x;i<=n;i+=lb(i)) c[i]=0;
}
int get(int x)
{
x++;
int s=0;
for(int i=x;i;i-=lb(i)) s+=c[i];
return s;
}
int get(int l,int r) { return get(r)-get(l-1); }
#undef lb
}
void dfs4(int u,int d,int x)
{
B::add(d,x);
for(int v:e[u]) if(v^fa[u]) dfs4(v,d+1,x);
}
void dfs3(int u)
{
B::add(0,1);
for(int v:e[u]) if((v^fa[u])&&(v^son[u])) dfs4(v,1,1);
for(auto t:g1[u])
{
int s=B::get(t.d)*t.x;
// cout<<" "<<t.id<<" "<<u<<" "<<t.d<<" "<<s<<endl;
ans[t.id]+=s;
}
for(int v:e[u])
{
if((v^fa[u])) dfs3(v);
}
B::add(0,-1);
for(int v:e[u]) if((v^fa[u])&&(v^son[u])) dfs4(v,1,-1);
}
void dfs6(int u,int x)
{
B::add(d[u],x);
for(int v:e[u]) if(v^fa[u]) dfs6(v,x);
}
void dfs5(int u,bool cs)
{
for(int v:e[u]) if((v^fa[u])&&(v^son[u])) dfs5(v,1);
if(son[u]) dfs5(son[u],0);
B::add(d[u],1);
for(int v:e[u]) if((v^fa[u])&&(v^son[u])) dfs6(v,1);
for(auto t:g2[u])
{
int s=B::get(d[u],d[u]+t.d)*t.x;
// cout<<" "<<t.id<<" "<<u<<" "<<t.d<<" "<<s<<endl;
ans[t.id]+=s;
}
if(cs)
{
For(k,dfn[u],ed[u]) B::cls(d[idfn[k]]);
}
}
void work1()
{
dfs3(1);
dfs5(1,1);
}
void Cls()
{
For(u,1,n) e[u].clear();
dct=0;
memset(ans,0,Q+2<<2);
For(u,1,n) d1[u].clear();
For(u,1,n) d2[u].clear();
memset(vs,0,n+2);
For(u,1,n) g1[u].clear();
For(u,1,n) g2[u].clear();
}
void work()
{
n=read();
For(i,1,n-1)
{
int u=read(),v=read();
e[u].pb(v);
e[v].pb(u);
}
pre1();
Q=read();
For(i,1,Q)
{
int u=read(),v=read(),d=read();
int lc=lca(u,v);
// cout<<lc<<endl;
solve(i,u,d,1);
solve(i,v,d,1);
solve(i,lc,d,-2);
ans[i]+=query1(lc,d);
// cout<<" "<<query1(u,d)<<" "<<query1(v,d)<<endl;
}
work1();
For(i,1,Q) printf("%d\n",ans[i]);
Cls();
}
signed main()
{
// freopen("ex_color.in","r",stdin);
// freopen("color.in","r",stdin);
// freopen("color.out","w",stdout);
int T=1;
while(T--) work();
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: 8ms
memory: 32064kb
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 1714 4981 12 1856 4825 4974 4974 19 82 4960 4680 208 4870 474 3693 808 1880 213 3394 1203 258 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 2577 15 49...
result:
wrong answer 18th numbers differ - expected: '1551', found: '1714'
Subtask #2:
score: 0
Wrong Answer
Test #9:
score: 0
Wrong Answer
time: 883ms
memory: 180020kb
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:
-8525 -55252 -28378 178011 81679 -1098 13497 199157 -110385 -117147 -96929 106609 -20219 -3518 -233 -109204 -208 -70887 145250 -92 -93956 192895 78055 -118502 152 68 -46235 -46212 199892 170799 56334 -446 1 3 2 3 3 -5 -41848 199899 199171 96354 196199 192866 -37364 -55003 143174 -34796 196172 199973...
result:
wrong answer 1st numbers differ - expected: '757', found: '-8525'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 728ms
memory: 152732kb
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 3851 96672 75 13429 149 58 704 199639 25 190454 489 198350 197627 10273 172193 191787 99 191654 80328 481 195140 173240 120515 288 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 7th numbers differ - expected: '3826', found: '3851'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%