QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#108420 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | fzj2007 | 0 | 1969ms | 379204kb | C++17 | 5.7kb | 2023-05-25 00:16:32 | 2023-05-25 00:16:36 |
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 f,int d,int id,int val){
if(x<1||x>n||d<0) return;
g2[dfn[f]-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];
if(p!=1){
insert1(p,d-1,id,-val);
insert1(son[fa[p]],d-1,id,val);
}
insert2(x,top[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) B.update(tmp.l,tmp.val);
for(auto tmp:g1[i])
if(tmp.id) ans[tmp.id]+=tmp.val*B.query(tmp.l,tmp.r);
}
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) B.update(tmp.l,tmp.val);
for(auto tmp:g2[i])
if(tmp.id) ans[tmp.id]+=tmp.val*B.query(tmp.l,tmp.r);
}
}
}
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;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 9ms
memory: 30140kb
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:
3226 2028 4988 208 252 3970 3886 2013 4974 2118 308 391 4768 312 4954 4988 4974 1551 4981 12 1856 4825 4974 2675 19 82 4960 4680 208 4870 474 3693 808 1880 213 3394 1203 266 84 4822 3334 70 81 4501 4960 668 4866 4974 113 490 75 163 209 2159 4981 4143 100 3168 232 66 4864 525 4958 390 4713 2305 15 26...
result:
wrong answer 24th numbers differ - expected: '4974', found: '2675'
Subtask #2:
score: 0
Wrong Answer
Test #9:
score: 0
Wrong Answer
time: 1969ms
memory: 379204kb
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: 1855ms
memory: 297144kb
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 107329 190250 5672 110415 199160 3826 96672 75 13429 149 58 704 199639 25 190454 489 198350 197627 10273 172193 192719 99 191654 80328 481 195140 170197 120515 290 199616 719 142 195166 2607 20737 135444 199768 2433 164666 180527 198261 14511 53672 69060 185790 110874 639 131 2130 188357 150164 2...
result:
wrong answer 28th numbers differ - expected: '170809', found: '170197'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%