QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#92076	#997. 2-SAT 问题	zhaohaikun^#	WA	60ms	80004kb	C++14	1.1kb	2023-03-30 10:19:56	2023-03-30 10:19:58

Judging History

This is the latest submission verdict.

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-03-30 10:19:58]
Judged

Verdict: WA
Time: 60ms
Memory: 80004kb

Show

[2023-03-30 10:19:56]
Submitted

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){
	T RR=1;FF=0;char CH=getchar();
	for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
	for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
	FF*=RR;
}
const int MAXN=3e6+10;
int n,m,a,b,a1,b1,dfn[MAXN],low[MAXN],tot,s[MAXN],sp,sccnum[MAXN],scccnt;
vector<int>E[MAXN];
void tarjan(int u){
	s[sp++]=u;
	dfn[u]=low[u]=++tot;
	for(auto v:E[u])
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(!sccnum[v]){
			low[u]=min(low[u],dfn[v]);
		}
	if(dfn[u]==low[u]){
		scccnt++;
		do{
			sccnum[s[--sp]]=scccnt;
		}while(s[sp]!=u);
	}
}
int main(){
	read(n);read(m);
	for(int i=1;i<=m;i++){
		read(a);read(a1);read(b);read(b1);
        E[a+(a1^1)*n].push_back(b+b1*n);
        E[b+(b1^1)*n].push_back(a+a1*n);
	}
	for(int i=1;i<=(n<<1);i++)
		if(!dfn[i])tarjan(i);
	for(int i=1;i<=(n<<1);i++)
		if(sccnum[i]==sccnum[i+n])return puts("No"),0;
	puts("Yes");
	for(int i=1;i<=n;i++)cout<<(sccnum[i]<sccnum[i+n])<<" ";
	return 0;
}
/*
3 1
1 1 3 0
*/

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0

Wrong Answer

time: 60ms

memory: 80004kb

input:

86354 86418
14615 0 14903 1
13605 0 4458 0
15604 0 77112 0
52311 1 64996 0
22711 1 74245 1
39042 1 57372 1
2994 1 84183 1
80574 0 58791 1
27780 1 9336 1
61809 0 7216 0
71113 0 42287 1
20073 0 72448 0
73840 0 77048 0
28955 0 4165 0
16322 1 14075 1
43512 0 58600 1
45219 0 53858 0
14919 0 22576 0
16594...

output:

Yes
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

result:

wrong answer Your plan didn't satisfy condition #1.(i = 14615, a = 0, j = 14903, b = 1)