QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#345122 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | ANIG | 0 | 55ms | 27428kb | C++14 | 3.1kb | 2024-03-06 09:48:29 | 2024-03-06 09:48:29 |
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,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){
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;
dfs3(c);
dep[c]=dep[x]+1;
siz[x]+=siz[c];
}
mk[x]=0;
}
void dfs4(int x,int y){
mk[x]=1;zx[x]=1e9;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]=min(zx[x],siz[c]);
}
zx[x]=min(zx[x],n-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[c.first-dep[x]]-jl[c.first-dep[x]];
}
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)return;
bk[x]=1;sm[0]=1;int MX=0;
dep[x]=0;
dfs3(x);
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);
dfs6(c);
MX=max(MX,mx);
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(){
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});
if(k==0)rs[i]=dep[x]+dep[y]-2*dep[c]+1;
}
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: 55ms
memory: 27428kb
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:
0 0 0 0 59 0 0 0 0 0 0 0 0 0 0 0 0 440 0 12 0 0 0 220 19 0 0 0 0 -8979 140 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 59 0 -8979 0 0 0 0 239 15 -4282 8 0 0 0 22 0 0 -8706 -1501 -7165 1317 0 -8835 0 -258 0 0 0 0 -348 16 0 19 0 0 0 12 220 0 -348 213 -8979 0 220 0 56 0 59 0 0 16 0 0 0 0 -36...
result:
wrong answer 1st numbers differ - expected: '3226', found: '0'
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:
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:
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%