QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#345135 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | ANIG | 0 | 351ms | 46196kb | C++14 | 3.5kb | 2024-03-06 10:15:34 | 2024-03-06 10:15:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n,m,mk[N],siz[N],zs[N],d[N],fa[N],dep[N],zd[N],cd[N],rs[N],bk[N],rt,zx[N],sm[N],mx,MX,jl[N];
vector<int>p[N];
vector<pair<int,int> >g[N];
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];
if(zd[c]+1>zd[x])cd[x]=zd[x],zd[x]=zd[c]+1;
else if(zd[c]+1>cd[x])cd[x]=zd[c]+1;
}
mk[x]=0;
}
void dfs2(int x,int y){
d[x]=y;mk[x]=1;
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);
}
}
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)];
// cout<<x<<" "<<sm[min(c.first-dep[x],MX)]<<" "<<MX<<endl;
}
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){
if(siz[x]==1){
for(int i=0;i<g[x].size();i++)rs[g[x][i].second]++;
return;
}
bk[x]=1;MX=0;
dep[x]=0;
dfs3(x);
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];
// cout<<"r"<<x<<endl;
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);
}
}
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);
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});
}
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: 6ms
memory: 27780kb
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:
2546 1004 4981 59 57 3369 3369 1004 4974 1719 59 171 4515 59 4952 4981 4974 1365 4981 1 1004 4780 4974 4974 1 13 4952 4515 59 4864 215 3369 472 1004 59 2546 472 131 13 4780 2546 13 13 4056 4952 171 4780 4974 13 171 13 59 59 1004 4981 3369 13 2546 57 13 4864 171 4952 59 4515 2087 1 4958 9 4056 3369 1...
result:
wrong answer 1st numbers differ - expected: '3226', found: '2546'
Subtask #2:
score: 0
Wrong Answer
Test #9:
score: 0
Wrong Answer
time: 351ms
memory: 46196kb
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 69427 2793 181264 91707 182 32495 199183 6399 15975 11640 119051 236 689 15 9532 39 36591 178936 55 45424 193403 90246 3417 949 68 34133 60471 199861 188090 75086 126 1 6 4 3 1 9 61156 199860 199151 155706 196287 192860 53742 51861 179199 428 196282 199989 3613 26 99007 134461 198159 20381 7517 ...
result:
wrong answer 2nd numbers differ - expected: '69428', found: '69427'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 284ms
memory: 45220kb
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:
12 100250 189419 1417 83887 199124 1908 83887 17 4321 12 4 71 199516 1 181342 71 197305 197305 4321 169235 192649 20 189419 77114 71 195121 170564 109022 100 199516 86 12 194525 354 14548 109022 199516 354 152872 169235 197305 10704 38072 54937 181342 100250 71 11 354 181342 132537 10574 181342 1995...
result:
wrong answer 1st numbers differ - expected: '78', found: '12'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%