QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#345168 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | ANIG | 0 | 43ms | 49792kb | C++14 | 6.0kb | 2024-03-06 12:10:25 | 2024-03-06 12:10:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
struct trs{
struct node{
int lson,rson,sm;
}p[N*20];
void upset(int x){
p[x].sm=p[p[x].lson].sm+p[p[x].rson].sm;
}
int idx;
void add(int x,int y,int d,int sm,int nl=0,int nr=2e5){
if(nl==nr){
p[y].sm=p[x].sm+sm;
return;
}
int mid=nl+nr>>1;
if(d<=mid){
p[y].lson=++idx;p[y].rson=p[x].rson;
add(p[x].lson,idx,d,sm,nl,mid);
}else{
p[y].rson=++idx;p[y].lson=p[x].lson;
add(p[x].rson,idx,d,sm,mid+1,nr);
}
upset(y);
}
int gets(int x,int l,int r,int nl=0,int nr=2e5){
if(!x||l>r)return 0;
if(l<=nl&&r>=nr)return p[x].sm;
int mid=nl+nr>>1;
if(r<=mid)return gets(p[x].lson,l,r,nl,mid);
if(l>mid)return gets(p[x].rson,l,r,mid+1,nr);
return gets(p[x].lson,l,r,nl,mid)+gets(p[x].rson,l,r,mid+1,nr);
}
}tr;
int idx,ts[N],gn[N],qz[N],n,m,mk[N],siz[N],zs[N],d[N],fa[N],dep[N],rs[N],bk[N],rt,zx[N],sm[N],mx,MX,jl[N],dfn[N],eds[N],dy[N],dp[N];
vector<int>p[N],f[N];
vector<pair<int,int> >g[N];
void dfs7(vector<int>&f,int x,int y){
f[dep[x]-dep[y]]++;mk[x]=1;
for(int i=0;i<p[x].size();i++){
int c=p[x][i];
if(mk[c])continue;
dfs7(f,c,y);
}
mk[x]=0;
}
void dfs1(int x){
mk[x]=1;siz[x]=1;
for(int i=0;i<p[x].size();i++){
int c=p[x][i];
if(mk[c])continue;
fa[c]=x;
dep[c]=dep[x]+1;
dfs1(c);
if(siz[c]>siz[zs[x]])zs[x]=c;
siz[x]+=siz[c];
}
int sz=0;
for(int i=0;i<p[x].size();i++){
int c=p[x][i];
if(mk[c]||c==zs[x])continue;
sz=max(sz,siz[c]);
}
f[x].resize(sz+1);
f[x][0]=1;
for(int i=0;i<p[x].size();i++){
int c=p[x][i];
if(mk[c]||c==zs[x])continue;
dfs7(f[x],c,x);
}
for(int i=1;i<f[x].size();i++)f[x][i]+=f[x][i-1];
mk[x]=0;
}
void dfs2(int x,int y){
d[x]=y;mk[x]=1;dfn[x]=++idx;dy[idx]=x;
dp[x]=dep[x]-dep[y];
if(zs[x])dfs2(zs[x],y);
for(int i=0;i<p[x].size();i++){
int c=p[x][i];
if(mk[c])continue;
dfs2(c,c);
}
eds[x]=idx;
}
int lca(int a,int b){
while(d[a]!=d[b]){
if(dep[d[a]]>dep[d[b]])swap(a,b);
b=fa[d[b]];
}
if(dep[a]>dep[b])swap(a,b);
return a;
}
void dfs3(int x){
MX=max(MX,dep[x]);
mk[x]=1;siz[x]=1;sm[dep[x]]++;
for(int i=0;i<p[x].size();i++){
int c=p[x][i];
if(mk[c]||bk[c])continue;
dep[c]=dep[x]+1;
dfs3(c);
siz[x]+=siz[c];
}
mk[x]=0;
}
void dfs4(int x,int y){
mk[x]=1;zx[x]=0;siz[x]=1;
for(int i=0;i<p[x].size();i++){
int c=p[x][i];
if(mk[c]||bk[c])continue;
dfs4(c,y);
siz[x]+=siz[c];
zx[x]=max(zx[x],siz[c]);
}
zx[x]=max(zx[x],y-siz[x]);
mk[x]=0;
if(!rt||zx[rt]>zx[x])rt=x;
}
void dfs5(int x){
mk[x]=1;mx=max(mx,dep[x]);jl[dep[x]]++;
for(int i=0;i<p[x].size();i++){
int c=p[x][i];
if(bk[c]||mk[c])continue;
dep[c]=dep[x]+1;
dfs5(c);
}
mk[x]=0;
}
void dfs6(int x){
mk[x]=1;
for(int i=0;i<g[x].size();i++){
auto c=g[x][i];
if(dep[x]>c.first)continue;
rs[c.second]+=sm[min(c.first-dep[x],MX)]-jl[min(c.first-dep[x],mx)];
}
for(int i=0;i<p[x].size();i++){
int c=p[x][i];
if(bk[c]||mk[c])continue;
dfs6(c);
}
mk[x]=0;
}
void solve(int x){
bk[x]=1;MX=0;
dep[x]=0;
dfs3(x);
if(siz[x]==1){
for(int i=0;i<g[x].size();i++)rs[g[x][i].second]++;
sm[0]=0;
return;
}
for(int i=1;i<=MX;i++)sm[i]+=sm[i-1];
for(int i=0;i<g[x].size();i++)rs[g[x][i].second]+=sm[min(g[x][i].first,MX)];
for(int i=0;i<p[x].size();i++){
int c=p[x][i];
if(bk[c])continue;
dep[c]=1;mx=0;
dfs5(c);
for(int j=1;j<=mx;j++)jl[j]+=jl[j-1];
dfs6(c);
for(int j=0;j<=mx;j++)jl[j]=0;
}
for(int i=0;i<=MX;i++)sm[i]=0;
for(int i=0;i<p[x].size();i++){
int c=p[x][i];
if(bk[c])continue;
rt=0;
dfs4(c,siz[c]);
solve(rt);
}
}
int gets(int x,int l,int r){
return tr.gets(gn[eds[x]],dep[x]+l,dep[x]+r)-tr.gets(gn[dfn[x]-1],dep[x]+l,dep[x]+r);
}
struct ask{
int k,op,bh;
};
vector<ask>gs[N];
int solve(int x,int k,int bh,int op){
int res=0;
while(x){
if(zs[x])res+=gets(zs[x],max(k-dp[x]-1,0ll),k-1);
gs[dfn[d[x]]-1].push_back({k,-op,bh});
gs[dfn[x]].push_back({k,op,bh});
x=fa[d[x]];
}
// cout<<k<<"-"<<res<<endl;
return res;
}
signed main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
p[x].push_back(y);
p[y].push_back(x);
}
dfs1(1);
dfs2(1,1);
for(int i=1;i<=n;i++){
gn[i]=++tr.idx;
tr.add(gn[i-1],gn[i],dep[dy[i]],1);
}
cin>>m;
for(int i=1;i<=m;i++){
int x,y,k,c;
cin>>x>>y>>k;
c=lca(x,y);
g[c].push_back({k,i});
rs[i]=solve(x,k,i,1)+solve(y,k,i,1)-solve(c,k,i,-2)*2;
}
for(int i=1;i<=n;i++){
for(int j=0;j<f[dy[i]].size()+dp[dy[i]]+1;j++){
qz[j]+=f[dy[i]][min((int)f[dy[i]].size()-1,j)];
if(j>dp[dy[i]])qz[j]-=f[dy[i]][min((int)f[dy[i]].size()-1,j-dp[dy[i]]-1)];
}
for(int j=0;j<gs[i].size();j++){
auto c=gs[i][j];
rs[c.bh]+=c.op*qz[c.k];
cout<<i<<" "<<c.bh<<" "<<c.op<<" "<<c.k<<" "<<qz[c.k]<<endl;
}
}
memset(mk,0,sizeof(mk));
solve(1);
for(int i=1;i<=m;i++)cout<<rs[i]<<"\n";
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 43ms
memory: 49792kb
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:
1 1 1 7 462 1 1 -2 7 462 1 2 1 5 311 1 2 -2 5 311 1 3 1 15 7 1 3 -2 15 7 1 4 1 2 39 1 4 -2 2 39 1 6 1 8 429 1 6 -2 8 429 1 7 1 8 429 1 7 -2 8 429 1 8 1 5 311 1 8 -2 5 311 1 9 1 14 16 1 9 -2 14 16 1 10 1 6 409 1 10 1 6 409 1 10 -2 6 409 1 11 1 2 39 1 11 -2 2 39 1 12 1 3 75 1 12 1 3 75 1 12 -2 3 75 1 ...
result:
wrong answer 1st numbers differ - expected: '3226', found: '1'
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:
1 1 1 10 12212 1 1 1 10 12212 1 1 -2 10 12212 1 3 1 18 906 1 3 1 18 906 1 3 -2 18 906 1 4 1 24 2 1 4 1 24 2 1 4 -2 24 2 1 5 1 23 9 1 5 1 23 9 1 5 -2 23 9 1 6 1 9 11262 1 6 1 9 11262 1 6 -2 9 11262 1 7 1 18 906 1 7 1 18 906 1 7 -2 18 906 1 8 1 30 0 1 8 1 30 0 1 8 -2 30 0 1 12 1 28 0 1 12 1 28 0 1 12 ...
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:
1 1 1 1 10 1 1 -2 1 10 1 3 1 16 5450 1 3 1 16 5450 1 3 -2 16 5450 1 4 1 4 764 1 4 -2 4 764 1 5 1 10 15502 1 5 -2 10 15502 1 7 1 5 1917 1 7 1 5 1917 1 7 -2 5 1917 1 8 1 10 15502 1 8 -2 10 15502 1 10 1 5 1917 1 10 -2 5 1917 1 11 1 1 10 1 11 -2 1 10 1 13 1 2 50 1 13 -2 2 50 1 14 1 20 475 1 14 -2 20 475...
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%