QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#108595#5020. 举办乘凉州喵,举办乘凉州谢谢喵Forza_Ferrari0 381ms307528kbC++143.4kb2023-05-25 17:31:342023-05-25 17:31: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 17:31:36]
  • 评测
  • 测评结果:0
  • 用时:381ms
  • 内存:307528kb
  • [2023-05-25 17:31:34]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n,m,ans[3000001],dep[3000001],fa[3000001],s[3000001],son[3000001],top[3000001],dfn[3000001],sum[3000005],cnt;
struct element
{
	int x,y,k,id;
}q[3000001];
vector<int> v[3000001];
struct opt
{
	int k,tag,id;
	opt(int k_,int tag_,int id_):
		k(k_),tag(tag_),id(id_){}
};
vector<opt> a[3000001];
struct ds
{
	int len[3000001],son[3000001],tmp[3000001],*id=tmp,*sum[3000001];
	vector<int> a[3000001],b[3000001];
	inline void dfs1(int k,int f)
	{
		for(int i:v[k])
		{
			if(i==f)
				continue;
			dfs1(i,k);
			if(len[i]>len[k])
			{
				len[k]=len[i];
				son[k]=i;
			}
		}
		++len[k];
	}
	inline void dfs2(int k,int f)
	{
		if(son[k])
		{
			sum[son[k]]=sum[k]+1;
			dfs2(son[k],k);
		}
		sum[k][0]+=s[k];
		for(int i:v[k])
		{
			if(i==f||i==son[k])
				continue;
			sum[i]=id;
			id+=len[i];
			dfs2(i,k);
			for(int j=0;j<len[i];++j)
				sum[k][j+1]+=sum[i][j];
		}
		for(int i:a[k])
		{
			ans[i]+=s[k];
			if(q[i].k+1<len[k])
				ans[i]-=sum[k][q[i].k+1];
			if(fa[top[k]]&&dep[fa[top[k]]]>=dep[q[i].x])
				a[fa[top[k]]].emplace_back(i);
		}
		for(int i:b[k])
		{
			ans[i]-=s[k];
			if(q[i].k<len[k])
				ans[i]+=sum[k][q[i].k];
			if(fa[top[fa[k]]]&&dep[fa[top[fa[k]]]]>=dep[q[i].x])
				b[top[fa[k]]].emplace_back(i);
		}
		a[k].clear();
		a[k].shrink_to_fit();
		b[k].clear();
		b[k].shrink_to_fit();
	}
}T;
inline void dfs1(int k,int f,int deep)
{
	dep[k]=deep;
	fa[k]=f;
	s[k]=1;
	for(int i:v[k])
	{
		if(i==f)
			continue;
		dfs1(i,k,deep+1);
		s[k]+=s[i];
		if(s[i]>s[son[k]])
			son[k]=i;
	}
}
inline void dfs2(int k,int t)
{
	top[k]=t;
	dfn[k]=++cnt;
	if(!son[k])
		return;
	dfs2(son[k],t);
	for(int i:v[k])
	{
		if(i==fa[k]||i==son[k])
			continue;
		dfs2(i,i);
	}
}
inline void update(int x,int y,int k,int id)
{
	T.a[y].emplace_back(id);
	if(x==y)
		return;
	bool flag=0;
	while(y==top[y])
	{
		if(!flag)
		{
			flag=1;
			T.b[y].emplace_back(id);
		}
		y=fa[y];
		if(y==x)
			return;
	}
	y=fa[y];
	while(top[x]^top[y])
	{
		a[y].emplace_back(k,1,id);
		y=top[y];
		while(y==top[y])
		{
			if(!flag)
			{
				flag=1;
				T.b[y].emplace_back(id);
			}
			y=fa[y];
			if(y==x)
				return;
		}
		y=fa[y];
	}
	a[y].emplace_back(k,1,id);
	if(x!=top[x])
		a[fa[x]].emplace_back(k,-1,id);
}
inline void dfs(int k,int f,int deep,int p)
{
	sum[deep]+=p*s[k];
	for(int i:v[k])
	{
		if(i==f)
			continue;
		dfs(i,k,deep+1,p);
	}
}
inline void init()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
}
inline int read()
{
	int x;
	cin>>x;
	return x;
}
int main()
{
	init();
	n=read();
	for(int i=1;i<n;++i)
	{
		int x=read(),y=read();
		v[x].emplace_back(y);
		v[y].emplace_back(x);
	}
	dfs1(1,0,1);
	dfs2(1,1);
	m=read();
	for(int i=1;i<=m;++i)
	{
		q[i].x=read(),q[i].y=read(),q[i].k=read();
		update(q[i].x,q[i].y,q[i].k,q[i].id=i);
	}
	T.dfs1(1,0);
	T.sum[1]=T.id;
	T.id+=T.len[1];
	T.dfs2(1,0);
	for(int i=1;i<=n;++i)
		if(top[i]==i)
		{
			int res=0;
			for(int j=i;j;j=son[j])
			{
				++res;
				for(int k:v[j])
					if(k!=son[j]&&k!=fa[j])
					{
						res+=s[k];
						dfs(k,j,1,1);
					}
				for(auto k:a[j])
					ans[k.id]+=k.tag*(res-sum[k.k+1]);
			}
			for(int j=i;j;j=son[j])
				for(int k:v[j])
					if(k!=son[j]&&k!=fa[j])
						dfs(k,j,1,-1);
		}
	for(int i=1;i<=m;++i)
		cout<<ans[i]<<'\n';
	cout.flush();
	return 0;
}

详细

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

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:


result:


Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 381ms
memory: 307528kb

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:

4
1
6
1
10
1
1
3
1
1
1
1
1
1
3
10
2
1
6
1
2
3
2
1
2
42
3
1
1
1
2
1
1
1
1
2
2
2
1
1
7
4
6
2
1
1
1
1
1
1
22
1
1
1
1
1
1
5
5
59
2
1
1
1
2
2
1
1
4
2
1
15
1
2
1
12
4
9
1
1
5
1
1
1
1
2
1
2
2
4
12
1
2
5
1
10
1
1
8
1
1
1
3
1
1
6
1
5
1
2
1
1
3
5
1
12
1
4
3
1
2
1
1
1
17
1
1
1
1
1
1
1
1
1
12
2
1
5
1
2
2
1
13
6...

result:

wrong answer 1st numbers differ - expected: '757', found: '4'

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%