QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#705051#6526. Canvaslllei#WA 27ms49572kbC++142.4kb2024-11-02 21:58:272024-11-02 21:58:33

Judging History

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

  • [2024-11-02 21:58:33]
  • 评测
  • 测评结果:WA
  • 用时:27ms
  • 内存:49572kb
  • [2024-11-02 21:58:27]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
vector<int>e[N],num[N];
bool vis[N],vis1[N];
int n,m;
int ans[N];
int s[N];
int d[N];
int fa[N];
vector<int>ans2,ans3;
vector<int> e1[N];
void dfs(int now)
{
	//cout<<now<<endl;
	ans[now]=2;
	vis[now]=1;
	int tmp=e[now].size();
	for(int i=0;i<tmp;i++)
		if(!vis[e[now][i]]){
			ans2.push_back(num[now][i]);
			dfs(e[now][i]);
		}
	else
		ans3.push_back(num[now][i]);
	return;
}
bool vis2[N];
bool flag;
queue<int>que;
int ifdag[N];
int find(int x)
{
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
int root;
void dfs1(int now)
{
	fa[now]=root;
	//if(ifdag[now]) return ;
	vis2[now]=1;
	que.push(now);
	int tmp=e[now].size();
	for(int i=0;i<tmp;i++)
	{
		if(!vis2[e[now][i]]) 
		{
			dfs1(e[now][i]);
			if(flag) return;
		}
		else
		{
		}
	}
	tmp=e1[now].size();
	for(int i=0;i<tmp;i++)
		if(!vis2[e1[now][i]]) 
			flag=false;
	
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		ans2.clear();ans3.clear();
		for(int i=1;i<=n;i++){
			vis[i]=0;vis1[i]=0;ans[i]=0;
			vis2[i]=0;
			s[i]=0;d[i]=0;
			e[i].clear();
			num[i].clear();
			ifdag[i]=0;
			fa[i]=i;
			e1[i].clear();
		}
		for(int i=1;i<=m;i++)
		{
			int l,x,r,y;
			cin>>l>>x>>r>>y;
			if(x>y) {
				swap(l,r);
				swap(x,y);
			}
			vis1[l]=vis1[r]=1;
			if(x==2&&y==2)
			{
				ans[l]=ans[r]=2;
				s[l]=1;s[r]=1;
				ans2.push_back(i);
			}
			if(x==1&&y==2)
			{
				e[l].push_back(r);
				num[l].push_back(i);
				e1[r].push_back(l);
				d[r]++;
			}
			if(x==1&&y==1)
				ans3.push_back(i);
		}
		for(int i=1;i<=n;i++){
			if(s[i]&&!vis[i]&&vis1[i])
				dfs(i);
		}
		for(int i=1;i<=n;i++)
			if(d[i]==0&&!vis[i]&&vis1[i])
			{
				dfs(i);
				ans[i]=1;
			}
		for(int i=1;i<=n;i++)
			if(!vis[i]&&vis1[i])
			{
				root=i;
				flag=true;
				dfs1(i);
				if(flag)
				{
				dfs(i);
				ans[i]=1;
				}
				else
				{
					ifdag[i]=1;
				}
			}
		while(!que.empty())
		{
			int now=que.front();que.pop();
			vis2[now]=0;
		}
		for(int i=1;i<=n;i++)
			if(vis1[i])
				ans[i]=max(ans[i],1);
		int ans1=0;
		for(int i=1;i<=n;i++)
		{
			ans1+=ans[i];
			//cout<<ans[i]<<' ';
		}
		cout<<ans1<<endl;
		int tmp=ans3.size();
		for(int i=0;i<tmp;i++)cout<<ans3[i]<<' ';
		tmp=ans2.size();
		for(int i=tmp-1;i>=0;i--)cout<<ans2[i]<<' ';
		cout<<endl;
	}
	return 0;	
}

详细

Test #1:

score: 100
Accepted
time: 7ms
memory: 49096kb

input:

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

output:

7
4 2 1 3 
5
2 1 

result:

ok Correct. (2 test cases)

Test #2:

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

input:

1
10 13
1 1 2 2
2 1 3 2
1 2 3 1
3 1 4 2
4 1 5 2
5 1 6 2
4 2 6 1
7 1 8 2
8 1 9 2
7 2 9 1
5 2 9 1
8 2 10 2
1 1 10 1

output:

19
13 8 5 3 4 2 1 7 6 11 10 9 12 

result:

ok Correct. (1 test case)

Test #3:

score: 0
Accepted
time: 3ms
memory: 49572kb

input:

1
7 5
2 1 6 2
1 2 6 1
1 1 5 1
2 2 7 1
1 1 7 2

output:

8
3 2 1 4 5 

result:

ok Correct. (1 test case)

Test #4:

score: 0
Accepted
time: 3ms
memory: 49540kb

input:

1
7 6
2 1 7 2
2 1 4 2
1 2 4 1
2 1 6 1
1 1 6 2
2 2 6 1

output:

9
4 3 2 1 6 5 

result:

ok Correct. (1 test case)

Test #5:

score: 0
Accepted
time: 7ms
memory: 48168kb

input:

1
7 5
5 2 7 1
5 1 6 2
3 2 7 1
3 2 6 1
6 1 7 2

output:

7
1 3 5 4 2 

result:

ok Correct. (1 test case)

Test #6:

score: 0
Accepted
time: 3ms
memory: 48768kb

input:

1
7 6
1 2 5 1
2 1 7 2
1 2 7 1
2 2 7 1
1 1 5 2
1 2 3 1

output:

8
1 3 4 2 5 6 

result:

ok Correct. (1 test case)

Test #7:

score: -100
Wrong Answer
time: 27ms
memory: 48620kb

input:

2000
15 16
2 2 3 1
12 2 15 1
3 2 9 1
6 2 14 1
2 1 15 2
5 2 6 1
7 1 10 1
9 2 15 1
2 2 3 1
4 2 12 1
2 2 9 1
5 2 8 2
3 2 13 1
12 1 13 2
9 2 13 1
5 1 14 2
15 15
5 2 11 1
1 2 8 1
8 1 15 2
6 2 8 2
8 2 9 1
1 1 6 2
6 1 9 2
2 2 5 1
2 1 10 2
7 2 10 1
1 1 15 2
5 2 15 1
7 1 11 2
1 1 2 1
5 2 9 1
15 14
3 1 5 2
1 ...

output:

23
7 6 1 9 3 11 8 15 13 14 10 2 5 4 16 12 
20
14 6 1 3 15 13 10 9 8 12 11 2 5 7 4 
21
2 14 6 11 13 10 3 9 12 7 8 4 1 5 
18
7 4 13 3 9 11 1 5 8 12 6 10 14 2 
20
6 5 3 2 7 11 1 12 18 16 19 9 14 10 13 17 8 4 15 
21
3 9 13 11 2 6 7 12 8 14 5 4 10 1 
21
3 15 7 11 8 14 1 5 2 9 6 13 4 12 10 
19
11 7 15 13 ...

result:

wrong answer Jury has better answer. Participant 20, jury 21 (test case 5)