QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#345162 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | ANIG | 0 | 1103ms | 162504kb | C++14 | 6.2kb | 2024-03-06 11:51:35 | 2024-03-06 11:51:36 |
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=1;i<f[x].size();i++)f[x][i]+=f[x][i-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);
}
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-dep[x]-1,0ll),k-1);
// gs[dfn[d[x]]-1].push_back({k,-op,bh});
// gs[dfn[x]].push_back({k,op,bh});
for(int i=dfn[d[x]];i<=dfn[x];i++){
res+=f[dy[i]][min(k,(int)f[dy[i]].size()-1)];
if(k>dp[dy[i]])res-=f[dy[i]][min(k-dp[dy[i]]-1,(int)f[dy[i]].size()-1)];
// cout<<dy[i]<<" "<<res<<endl;
}
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();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";
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 14ms
memory: 27204kb
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:
3018 1208 4983 171 183 3087 3158 1269 4968 2020 245 337 4355 247 4955 4995 4963 1529 4981 12 1412 4870 4966 4974 19 82 4881 4646 172 4857 365 3691 775 1487 177 2947 845 184 84 4861 2847 70 81 4235 4929 450 4529 4968 113 381 75 136 165 1288 4976 3179 100 2969 173 66 4875 393 4897 300 4530 1924 15 495...
result:
wrong answer 1st numbers differ - expected: '3226', found: '3018'
Subtask #2:
score: 0
Time Limit Exceeded
Test #9:
score: 8
Accepted
time: 950ms
memory: 153804kb
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: 985ms
memory: 162504kb
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: 1103ms
memory: 152344kb
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 100046 191004 4179 94438 199013 2212 85952 75 9713 149 58 572 199584 25 178211 410 197101 197994 8022 171593 192241 99 189554 78336 410 194887 170964 116880 242 199542 573 142 195779 1930 18427 121390 199929 1827 164333 176048 196917 12528 48164 52799 181434 96180 525 131 1621 175598 126960 16155...
result:
wrong answer 2nd numbers differ - expected: '107329', found: '100046'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%