QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#108408 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | fzj2007 | 0 | 1657ms | 302856kb | C++17 | 5.6kb | 2023-05-24 22:14:37 | 2023-05-24 22:14:38 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &x){
x=0;
char ch=getchar();
bool flag=0;
while(ch>'9'||ch<'0') flag=flag||ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
x=flag?-x:x;
}
template<typename T,typename ...Args>inline void read(T &x,Args &...args){
read(x),read(args...);
}
template<typename T>inline void prt(T x){
if(x>9) prt(x/10);
putchar(x%10+'0');
}
template<typename T>inline void put(T x){
if(x<0) putchar('-'),x=-x;
prt(x);
}
template<typename T>inline void put(char ch,T x){
put(x),putchar(ch);
}
template<typename T,typename ...Args>inline void put(char ch,T x,Args ...args){
put(ch,x),put(ch,args...);
}
#define N 200005
int n,q,ans[N];
int head[N],cnt;
struct edge{
int v,nxt;
}e[N<<1];
inline void add(int u,int v){
e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}
namespace Devide{
vector<pair<int,int> >ques[N];
bool vis[N];
inline int get_siz(int x,int fa){
if(vis[x]) return 0;
int siz=1;
for(int i=head[x];i;i=e[i].nxt)
if(e[i].v!=fa) siz+=get_siz(e[i].v,x);
return siz;
}
inline int get_wc(int x,int fa,int sum,int &wc){
if(vis[x]) return 0;
int siz=1,ms=0;
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].v,t;
if(v==fa) continue;
t=get_wc(v,x,sum,wc),ms=max(ms,t),siz+=t;
}
ms=max(ms,sum-siz);
if(ms<=sum/2) wc=x;
return siz;
}
int t[N],maxlen,p[N],nowlen;
inline void get_dist(int x,int fa,int dep,vector<pair<int,int> >& ins){
if(vis[x]) return;
nowlen=max(nowlen,dep),p[dep]++,ins.emplace_back(x,dep);
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
if(v==fa) continue;
get_dist(v,x,dep+1,ins);
}
}
inline void devide(int x){
if(vis[x]) return;
get_wc(x,0,get_siz(x,0),x),vis[x]=1;
maxlen=0,t[0]++;
vector<pair<int,int> > all;
all.emplace_back(x,0);
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
if(vis[v]) continue;
vector<pair<int,int> > ins;
nowlen=0,get_dist(v,x,1,ins);
for(int j=1;j<=nowlen;j++) p[j]+=p[j-1];
for(auto val:ins){
int u=val.first,d=val.second;
for(auto tmp:ques[u])
if(tmp.first>=d) ans[tmp.second]-=p[tmp.first-d];
all.emplace_back(val);
}
for(int j=nowlen;j;j--) p[j]-=p[j-1];
maxlen=max(maxlen,nowlen);
for(int j=0;j<=nowlen;j++) t[j]+=p[j],p[j]=0;
}
for(int i=1;i<=maxlen;i++) t[i]+=t[i-1];
for(auto val:all){
int u=val.first,d=val.second;
for(auto tmp:ques[u])
if(tmp.first>=d) ans[tmp.second]+=t[tmp.first-d];
}
for(int i=0;i<=maxlen;i++) t[i]=0;
for(int i=head[x];i;i=e[i].nxt) devide(e[i].v);
}
inline void solve(){
memset(vis,0,sizeof(vis));
memset(t,0,sizeof(t));
devide(1);
}
}
namespace Chain{
int fa[N],dfn[N],dep[N],top[N],idx,son[N],siz[N];
struct BIT{
int c[N];
BIT(){memset(c,0,sizeof(c));}
#define lowbit(X) (X&-X)
inline void update(int x,int v){
for(;x<=n+1;x+=lowbit(x)) c[x]+=v;
}
inline int query(int x){
int res=0;
for(;x;x^=lowbit(x)) res+=c[x];
return res;
}
inline int query(int l,int r){
return query(r)-query(l-1);
}
#undef lowbit
}B;
inline void dfs1(int x,int fat){
fa[x]=fat,dep[x]=dep[fat]+1,siz[x]=1;
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
if(v==fat) continue;
dfs1(v,x),siz[x]+=siz[v];
if(siz[son[x]]<siz[v]) son[x]=v;
}
}
inline void dfs2(int x,int tf){
top[x]=tf,dfn[x]=++idx;
if(son[x]) dfs2(son[x],tf);
for(int i=head[x];i;i=e[i].nxt)
if(e[i].v!=son[x]&&e[i].v!=fa[x]) dfs2(e[i].v,e[i].v);
}
inline int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
return x;
}
struct Ques{
int l,r,id,val;
Ques(){}
Ques(int _l,int _r,int _id,int _val):l(_l),r(_r),id(_id),val(_val){}
};
vector<Ques> g1[N];
vector<Ques> g2[N];
inline void insert1(int x,int d,int id,int val){
if(x<1||x>n||d<0) return;
g1[dfn[x]-1].emplace_back(dep[x],min(dep[x]+d,n),id,-val);
g1[dfn[x]+siz[x]-1].emplace_back(dep[x],min(dep[x]+d,n),id,val);
}
inline void insert2(int x,int d,int id,int val){
if(x<1||x>n||d<0) return;
g2[dfn[top[x]]-1].emplace_back(1,d+1,id,-val);
g2[dfn[x]].emplace_back(1,d+1,id,val);
}
inline void insert(int x){
int d=dep[x];
while(x){
g2[dfn[x]].emplace_back(d-dep[x]+1,0,0,1);
x=fa[top[x]];
}
}
inline void update(int x,int d,int id,int val){
insert1(son[x],d-1,id,val);
while(x){
int p=top[x];
insert1(p,d-1,id,-val);
// insert1(son[fa[p]],d-1,id,val);
insert2(x,d,id,val);
x=fa[p];
}
}
inline void prework(){
memset(fa,0,sizeof(fa));
memset(dfn,0,sizeof(dfn));
memset(dep,0,sizeof(dep));
memset(top,0,sizeof(top));
memset(son,0,sizeof(son));
memset(siz,0,sizeof(siz));
idx=0;
dfs1(1,0),dfs2(1,1);
}
inline void solve(){
B=BIT();
for(int i=1;i<=n;i++) g1[dfn[i]].emplace_back(dep[i],0,0,1);
for(int i=1;i<=n;i++){
for(auto tmp:g1[i]){
if(tmp.id) ans[tmp.id]+=tmp.val*B.query(tmp.l,tmp.r);
else B.update(tmp.l,tmp.val);
}
}
B=BIT();
for(int i=1;i<=n;i++) insert(i);
for(int i=1;i<=n;i++){
for(auto tmp:g2[i]){
if(tmp.id) ans[tmp.id]+=tmp.val*B.query(tmp.l,tmp.r);
else B.update(tmp.l,tmp.val);
}
}
}
}
int main(){
read(n);
for(int i=1,u,v;i<n;i++) read(u,v),add(u,v),add(v,u);
read(q),Chain::prework();
for(int i=1,x,y,d;i<=q;i++){
read(x,y,d);
int z=Chain::lca(x,y);
Devide::ques[z].emplace_back(d,i);
Chain::update(x,d,i,1);
Chain::update(y,d,i,1);
Chain::update(z,d,i,-2);
}
Devide::solve();
Chain::solve();
for(int i=1;i<=q;i++) put('\n',ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 22ms
memory: 28892kb
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:
1003 1820 4940 174 159 3804 3847 1347 2291 -124 232 26 2660 222 -11 -1812 4905 726 1401 12 828 -796 3923 552 19 63 4939 -835 144 3796 344 -442 -98 468 124 960 566 254 60 -754 2020 48 66 1666 2645 433 4708 2448 105 54 50 109 108 1869 3804 3478 75 1113 127 42 2749 207 4785 333 1420 1553 15 2554 59 -15...
result:
wrong answer 1st numbers differ - expected: '3226', found: '1003'
Subtask #2:
score: 0
Wrong Answer
Test #9:
score: 0
Wrong Answer
time: 1657ms
memory: 302856kb
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 69086 2307 174594 87618 182 31912 174485 6313 15724 11640 115209 219 689 9 9389 16 36017 175381 46 44726 177340 89680 3334 949 68 33944 59516 175163 188090 75088 127 1 3 3 2 3 9 61157 171749 193983 155706 196287 192862 53145 51862 172051 347 196282 199989 3543 12 99007 134461 191404 20166 7420 1...
result:
wrong answer 2nd numbers differ - expected: '69428', found: '69086'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 1518ms
memory: 250120kb
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:
41 96024 22772 3972 55242 172160 3200 64091 58 6709 101 48 463 159809 25 176960 193 231412 29969 1698 26548 164439 60 156151 46623 117 182772 146770 7276 258 179241 631 75 -459 1976 14692 7811 -23026 1324 96068 -15290 197691 9622 -2324 69502 157074 106015 423 62 1097 231666 153799 7884 157917 126566...
result:
wrong answer 1st numbers differ - expected: '78', found: '41'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%