QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#704821#6526. Canvaslllei#WA 7ms33316kbC++141.6kb2024-11-02 21:08:442024-11-02 21:08:45

Judging History

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

  • [2024-11-02 21:08:45]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:33316kb
  • [2024-11-02 21:08:44]
  • 提交

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];
vector<int>ans2,ans3;
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;
}
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;
			s[i]=0;d[i]=0;
			e[i].clear();
			num[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);
				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])
			{
				dfs(i);
				ans[i]=1;
			}
		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: 0ms
memory: 33048kb

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: 32380kb

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: 0ms
memory: 31980kb

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: 7ms
memory: 33316kb

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: -100
Wrong Answer
time: 4ms
memory: 33076kb

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:

6
4 1 3 5 2 

result:

wrong answer Participant's solution is incorrect. (test case 1)