QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#345134 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | ANIG | 0 | 395ms | 46172kb | C++14 | 3.5kb | 2024-03-06 10:11:03 | 2024-03-06 10:11:04 |
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]=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],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: 4ms
memory: 27672kb
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
Time Limit Exceeded
Test #9:
score: 8
Accepted
time: 395ms
memory: 46172kb
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: 231ms
memory: 44936kb
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: 329ms
memory: 45676kb
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 6 71 199516 1 181342 71 197305 197305 4321 169235 192649 20 189419 77114 71 195121 170566 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%