QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#90582 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | OtoriEmu | 0 | 1182ms | 98008kb | C++14 | 4.7kb | 2023-03-23 20:05:32 | 2023-03-23 20:05:33 |
Judging History
answer
/*
¤ï¤ó¤ï¤ó¡¡¤ï¤ó¤À¤Û©`¤¤¤Ã¡î
Wonderhoy!
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;
char buf[1<<21],*p1=buf,*p2=buf;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++)
int read()
{
int x=0;
char c=getchar();
while(c<'0' || c>'9') c=getchar();
while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
return x;
}
void write(int x)
{
if(x>9) write(x/10);
putchar(x%10+'0');
}
typedef pair<int,int> P;
typedef vector<int> Poly;
typedef vector<P> PolyP;
#define mp make_pair
#define spc putchar(' ')
#define etr putchar('\n')
#define inlp(x,y) putchar(x==y?'\n':' ')
Poly G[200005];
int fa[19][200005];
#define F(u) fa[0][u]
int dep[200005],son[200005],siz[200005],h[200005];
void dfs1(int u,int f)
{
F(u)=f;
dep[u]=dep[f]+1;
siz[u]=1;
for(int v:G[u])
{
if(v==f) continue;
dfs1(v,u),siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
h[u]=max(h[u],h[v]+1);
}
}
int top[200005];
void dfs2(int u,int t)
{
top[u]=t;
if(son[u]) dfs2(son[u],t);
for(int v:G[u]) if((v^F(u)) && (v^son[u])) dfs2(v,v);
}
int n,q;
int ans[200005];
inline int lowbit(int x){return x&(-x);}
namespace subt1
{
int mx[200005],rt,s,sz[200005];
PolyP qry[200005];
bool del[200005];
void getrt(int u,int f)
{
siz[u]=1,mx[u]=0;
for(int v:G[u])
{
if(v==f || del[v]) continue;
getrt(v,u);
siz[u]+=siz[v];
mx[u]=max(mx[u],sz[v]);
}
mx[u]=max(mx[u],s-siz[u]);
if(mx[u]<mx[rt]) rt=u;
}
int dp[200005];
int cnt[200005];
Poly subt;
int up;
void dfs(int u,int f)
{
++cnt[dp[u]];
up=max(up,dp[u]),subt.push_back(u);
for(int v:G[u])
{
if(v==f || del[v]) continue;
dp[v]=dp[u]+1;
dfs(v,u);
}
}
void solve(int u,int f,int coef)
{
subt.clear(),up=0;
dfs(u,f);
for(int i=1;i<=up;++i) cnt[i]+=cnt[i-1];
for(int p:subt)
{
for(P st:qry[p])
{
int d=st.first,id=st.second;
if(d>=dp[p]) ans[id]+=coef*cnt[min(up,d-dp[p])];
}
}
for(int i=0;i<=up;++i) cnt[i]=0;
}
void solve(int u)
{
del[u]=true,dp[u]=0;
solve(u,0,1);
for(int v:G[u]) if(!del[v]) solve(v,u,-1);
for(int v:G[u])
{
if(del[v]) continue;
getrt(v,u);
s=siz[v],rt=0;
getrt(v,u);
solve(rt);
}
}
void solve()
{
mx[rt=0]=1e9;
s=n,getrt(1,0);
solve(rt);
}
}
namespace subt2
{
PolyP qry[200005];
void add(int u,int v,int d,int id)
{
while(top[u]^top[v])
{
if(son[u]) qry[son[u]].emplace_back(d,-id);
qry[top[u]].emplace_back(d,id);
u=F(top[u]);
}
if(son[u]) qry[son[u]].emplace_back(d,-id);
if(son[v]) qry[son[v]].emplace_back(d,id); // son of v -> u
}
int *f[200005],dp[400005],*now=dp;
int tr[400005];
const int N=4e5;
int ver[400005],vc;
void modify(int x,int w)
{
for(int i=x;i;i^=lowbit(i))
{
if(ver[i]^vc) ver[i]=vc,tr[i]=0;
tr[i]+=w;
}
}
int query(int x)
{
int ans=0;
for(int i=x;i<=N;i+=lowbit(i))
{
if(ver[i]^vc) ver[i]=vc,tr[i]=0;
ans+=tr[i];
}
return ans;
}
void dfs(int u)
{
f[u][0]=1;
if(son[u]) f[son[u]]=f[u]+1,dfs(son[u]);
for(int v:G[u])
{
if(v==F(u) || v==son[u]) continue;
f[v]=now,now+=h[v]+1;
dfs(v);
for(int i=0;i<=h[v];++i) f[u][i+1]+=f[u][i];
}
if(u==top[u])
{
#undef F
vector<PolyP> E(h[u]+1),F(h[u]+1);
int cnt=0;
for(int x=u;x;x=son[x])
{
++cnt;
for(P st:qry[x])
{
int d=st.first,id=st.second;
if(d<=h[x]) E[d].emplace_back(cnt+d,id);
}
F[0].emplace_back(1,cnt);
for(int y:G[x])
{
if(y==son[x] || y==fa[0][x]) continue;
for(int i=0;i<=h[y];++i) F[i+1].emplace_back(f[y][i],cnt+i+1);
}
}
++vc;
for(int i=0;i<=h[u];++i)
{
for(P st:F[i]) modify(st.second,st.first);
for(P st:E[i])
{
int d=st.first,id=st.second;
if(id<0) ans[-id]-=query(d);
else ans[id]+=query(d);
}
}
}
}
inline void solve(){f[1]=now,now+=h[1]+1,dfs(1);}
}
int LCA(int u,int v)
{
if(dep[u]>dep[v]) swap(u,v);
while(dep[u]<dep[v]) v=fa[__lg(dep[v]-dep[u])][v];
if(u==v) return u;
for(int i=18;~i;--i) if(fa[i][u]^fa[i][v]) u=fa[i][u],v=fa[i][v];
return fa[0][u];
}
int main(){
n=read();
for(int i=1;i<n;++i)
{
int u=read(),v=read();
G[u].push_back(v);
G[v].push_back(u);
}
q=read();
dfs1(1,0),dfs2(1,1);
for(int i=1;i<=18;++i) for(int j=1;j<=n;++j) fa[i][j]=fa[i-1][fa[i-1][j]];
for(int i=1;i<=q;++i)
{
int u=read(),v=read(),d=read();
int p=LCA(u,v);
subt1::qry[p].emplace_back(d,i);
subt2::add(u,p,d,i),subt2::add(v,p,d,i);
}
subt1::solve(),subt2::solve();
for(int i=1;i<=q;++i) write(ans[i]),etr;
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: 19372kb
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:
13082 3877 4988 208 252 17959 17286 3825 4974 2846 308 406 24967 312 4955 4988 4974 1963 4981 12 3713 4918 4974 4974 19 82 5257 8135 208 5166 498 6369 942 2955 213 13617 1727 279 84 4869 14072 70 81 28165 5257 742 12163 4974 113 526 75 163 209 4529 4981 19655 100 11799 232 66 4864 583 5254 390 22812...
result:
wrong answer 1st numbers differ - expected: '3226', found: '13082'
Subtask #2:
score: 0
Time Limit Exceeded
Test #9:
score: 8
Accepted
time: 849ms
memory: 57144kb
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: 0
Accepted
time: 381ms
memory: 55808kb
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
Time Limit Exceeded
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:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 1182ms
memory: 98008kb
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 1963372 5135952 8555 13713491 755865 8260 9786401 75 30734 149 58 704 309062316 25 377199306 489 400076098 4516964 22399 9329872 572536 99 326633472 239993 481 401133 450976 5018334 290 293395005 719 142 54837618 2996 87451 17544284 147787607 2711 112257565 114478542 383963537 35969 660404 945118...
result:
wrong answer 2nd numbers differ - expected: '107329', found: '1963372'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%