QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#108420#5020. 举办乘凉州喵,举办乘凉州谢谢喵fzj20070 1969ms379204kbC++175.7kb2023-05-25 00:16:322023-05-25 00:16:36

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-25 00:16:36]
  • 评测
  • 测评结果:0
  • 用时:1969ms
  • 内存:379204kb
  • [2023-05-25 00:16:32]
  • 提交

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%