QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#165506#6559. A Tree and Two EdgesPhantomThreshold#WA 361ms11168kbC++203.3kb2023-09-05 18:59:272023-09-05 18:59:28

Judging History

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

  • [2023-09-05 18:59:28]
  • 评测
  • 测评结果：WA
  • 用时：361ms
  • 内存：11168kb
查看
  • [2023-09-05 18:59:27]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxd=15;
int main()
{
	ios_base::sync_with_stdio(false);
	int n,q;
	cin>>n>>q;
	vector<vector<int>> G(n+5);
	for(int i=1;i<=n+1;i++)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	vector<int> dep(n+5,-1),vis(n+5),pa(n+5),L(n+5),R(n+5);
	int ind=0;
	vector<pair<int,int>> ex;
	function<void(int,int)> dfs=[&](int u,int p)
	{
		vis[u]=1;
		L[u]=++ind;
		for(auto v:G[u])
		{
			if(v==p)continue;
			if(not vis[v])
			{
				pa[v]=u;
				dep[v]=dep[u]+1;
				dfs(v,u);
			}
			else if(vis[v]==1)
			{
				ex.emplace_back(u,v);
			}
		}
		vis[u]=2;
		R[u]=ind;
	};
	dep[1]=0;
	dfs(1,0);
	vector<vector<int>> jmp(maxd+5,vector<int>(n+5));
	for(int i=1;i<=n;i++)jmp[0][i]=pa[i];
	for(int d=1;d<=maxd;d++)
	{
		for(int i=1;i<=n;i++)
		{
			jmp[d][i]=jmp[d-1][jmp[d-1][i]];
		}
	}
	auto getlca=[&](int u,int v)
	{
		if(dep[u]>dep[v])swap(u,v);
		for(int d=maxd;d>=0;d--)
			if(dep[jmp[d][v]]>=dep[u])
				v=jmp[d][v];
		if(u==v)return u;
		for(int d=maxd;d>=0;d--)
			if(jmp[d][u]!=jmp[d][v])
				u=jmp[d][u],v=jmp[d][v];
		return pa[u];
	};
	auto onpath=[&](int l,int p,int x)
	{
		return L[p]<=L[x] and R[x]<=R[p] and L[x]<=L[l] and R[l]<=R[x];
	};
	auto intersect=[&](int a,int b,int c,int d)
	{
		int l1=getlca(a,b),l2=getlca(c,d);
		return onpath(a,l1,l2) or onpath(b,l1,l2) or onpath(c,l2,l1) or onpath(d,l2,l1);
	};
	auto checkpaths=[&](const vector<pair<int,int>> &vec)
	{
		int sz=vec.size();
		for(int i=0;i<sz;i++)
			for(int j=i+1;j<sz;j++)
				if(intersect(vec[i].first,vec[i].second,vec[j].first,vec[j].second))
					return false;
		return true;
	};
	auto [a,b]=ex[0];
	auto [c,d]=ex[1];
//	cerr<<"extra edges: "<<ex.size()<<" - "<<a<<' '<<b<<' '<<c<<' '<<d<<endl;
	while(q--)
	{
		int u,v;
		cin>>u>>v;
		int cnt=1;
		
		if(checkpaths({make_pair(u,a),make_pair(b,v)}))cnt++;
		if(checkpaths({make_pair(u,b),make_pair(a,v)}))cnt++;
		if(checkpaths({make_pair(u,c),make_pair(d,v)}))cnt++;
		if(checkpaths({make_pair(u,d),make_pair(c,v)}))cnt++;
		
		if(checkpaths({make_pair(u,a),make_pair(b,c),make_pair(d,v)}))cnt++;
		if(checkpaths({make_pair(u,a),make_pair(c,b),make_pair(d,v)}))cnt++;
		if(checkpaths({make_pair(u,b),make_pair(a,c),make_pair(d,v)}))cnt++;
		if(checkpaths({make_pair(u,c),make_pair(a,b),make_pair(d,v)}))cnt++;
		if(checkpaths({make_pair(u,a),make_pair(b,d),make_pair(c,v)}))cnt++;
		if(checkpaths({make_pair(u,a),make_pair(c,d),make_pair(b,v)}))cnt++;
		if(checkpaths({make_pair(u,b),make_pair(a,d),make_pair(c,v)}))cnt++;
		if(checkpaths({make_pair(u,c),make_pair(a,d),make_pair(b,v)}))cnt++;
		
		swap(a,c);swap(b,d);
		if(checkpaths({make_pair(u,a),make_pair(b,c),make_pair(d,v)}))cnt++;
		if(checkpaths({make_pair(u,a),make_pair(c,b),make_pair(d,v)}))cnt++;
		if(checkpaths({make_pair(u,b),make_pair(a,c),make_pair(d,v)}))cnt++;
		if(checkpaths({make_pair(u,c),make_pair(a,b),make_pair(d,v)}))cnt++;
		if(checkpaths({make_pair(u,a),make_pair(b,d),make_pair(c,v)}))cnt++;
		if(checkpaths({make_pair(u,a),make_pair(c,d),make_pair(b,v)}))cnt++;
		if(checkpaths({make_pair(u,b),make_pair(a,d),make_pair(c,v)}))cnt++;
		if(checkpaths({make_pair(u,c),make_pair(a,d),make_pair(b,v)}))cnt++;
		swap(a,c);swap(b,d);
		
		cout<<cnt<<"\n";
	}
	return 0;
}
源文件, 语言: C++20

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3640kb

input:

4 6
1 2
1 3
1 4
2 3
2 4
1 2
1 3
1 4
2 3
2 4
3 4

output:

3
3
3
3
3
4

result:

ok 6 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

6 4
1 2
1 3
1 6
2 3
3 4
3 5
4 5
1 2
1 3
1 4
1 6

output:

2
2
4
1

result:

ok 4 lines

Test #3:

score: 0
Accepted
time: 361ms
memory: 11168kb

input:

50000 50000
11561 23122
14261 28523
24407 48814
17947 35894
14803 29607
19557 39115
12415 24830
9583 19167
18397 36794
439 878
18040 36080
17150 34300
7922 15845
18938 37877
18625 37250
6459 12919
9818 19636
3579 7158
21323 42646
23882 47764
13603 27207
8353 16707
15907 31814
20935 41871
11686 23372...

output:

4
3
3
4
4
3
1
3
4
1
3
4
3
4
3
3
1
3
3
3
4
4
4
3
3
3
4
3
3
3
1
3
3
3
3
4
4
4
4
3
4
3
3
3
4
3
4
4
4
4
3
4
4
4
4
3
3
3
4
4
4
4
4
4
3
4
3
4
1
4
1
1
4
3
3
4
3
3
1
4
3
3
4
4
3
3
4
4
4
3
4
3
4
4
4
4
4
3
4
3
3
3
1
3
4
4
3
4
3
4
3
3
4
1
4
3
3
3
4
4
4
4
3
3
3
3
3
4
4
4
4
3
3
4
3
4
4
3
3
4
4
4
1
3
3
3
3
4
4
3
...

result:

ok 50000 lines

Test #4:

score: -100
Wrong Answer
time: 315ms
memory: 10980kb

input:

50000 50000
1730 3460
17535 35071
14108 28216
20630 41260
2091 4182
8112 16225
21373 42746
6685 13371
21142 42284
12168 24337
22564 45128
16103 32207
9254 18508
21369 42739
1955 3911
13696 27392
3929 7858
1777 3555
23382 46764
830 1660
17722 35444
11495 22991
10184 20369
13697 27395
24728 49456
4037...

output:

1
1
3
5
3
4
4
4
4
4
3
3
5
4
1
3
4
3
3
1
5
3
4
3
1
4
5
5
4
5
5
4
4
4
1
1
4
1
5
4
3
1
4
4
3
5
3
4
1
4
4
1
3
1
3
3
3
1
1
3
3
3
5
3
4
3
4
4
3
3
4
4
4
3
3
4
4
4
3
4
3
5
5
3
5
5
3
3
4
4
1
4
3
4
1
4
4
4
4
3
4
1
4
4
3
4
3
4
3
4
3
1
4
3
1
1
5
5
4
4
1
5
3
5
4
3
3
4
4
4
4
4
3
3
4
3
4
1
1
3
4
4
3
4
4
3
3
4
4
5
...

result:

wrong answer 4th lines differ - expected: '3', found: '5'
English 繁體中文 简体中文

伺服器時間: 2024-12-03 00:46:05 | 開源專案