QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#147525#6633. Exam RequirementsqzezWA 16ms208788kbC++142.7kb2023-08-23 12:03:162023-08-25 01:38:08

Judging History

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

  • [2023-08-25 01:38:08]
  • 评测
  • 测评结果:WA
  • 用时:16ms
  • 内存:208788kb
  • [2023-08-23 12:03:16]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=2e5+5,M=N*40+5,K=14348907+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const ll INF=1e18+7;mt19937 rnd(time(0));
int n,m,A[N],B[N];
vector<pii> Id[N];
vector<int> S[M];
int Ct,SCC;
void con(int x,int y){S[x].emplace_back(y);}
pair<int,int*> Ns[N];int Nh;
namespace CT{
	int CC,L[M],R[M],I1[M],I2[M];
	void Cl(){for(int i=1;i<=CC;i++) L[i]=R[i]=I1[i]=I2[i]=0;CC=0;}
	void CP(int &v){L[++CC]=L[v];R[CC]=R[v];I1[CC]=++Ct;I2[CC]=++Ct;if(v) con(I1[CC],I1[v]),con(I2[v],I2[CC]);v=CC;}
	void add(int x,int id,int &v,int l=1,int r=Nh){
		if(!v) CP(v);con(I1[v],id+n);con(id,I2[v]);if(l==r) return;
		int m=l+r>>1;x<=m?add(x,id,L[v],l,m):add(x,id,R[v],m+1,r);
	}
	void qry(int x,int y,int id,int v,int l=1,int r=Nh){
		if(!v) return;
		if(x<=l&&r<=y) return con(id,I1[v]),con(I2[v],id+n);int m=l+r>>1;
		x<=m&&(qry(x,y,id,L[v],l,m),0);y>m&&(qry(x,y,id,R[v],m+1,r),0);
	}
}
int scc[M];
namespace Tarjan{
	int dfn[M],low[M],dh,st[M],sh,vis[M];
	void Cl(){for(int i=1;i<=Ct;i++) dfn[i]=low[i]=vis[i]=st[i]=scc[i]=0;dh=sh=0;}
	void Tarjan(int x){
		dfn[x]=low[x]=++dh;st[++sh]=x;vis[x]=1;for(int i:S[x]){
			if(!dfn[i]) Tarjan(i),low[x]=min(low[x],low[i]);else if(vis[i]) low[x]=min(low[x],dfn[i]);
		}if(dfn[x]<=low[x]) {SCC++;while(st[sh+1]^x) vis[st[sh]]=0,scc[st[sh--]]=SCC;}
	}
	void BD(){for(int i=1;i<=Ct;i++) if(!dfn[i]) Tarjan(i);}
}
int Ro[N];
void Solve(){
	int i,j;
	for(i=1;i<=Nh;i++) Id[i].clear();Nh=0;
	for(i=1;i<=Ct;i++) S[i].clear();Tarjan::Cl();Ct=SCC=0;CT::Cl();
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++) scanf("%d%d",&A[i],&B[i]),Ns[++Nh]=make_pair(A[i],&A[i]),Ns[++Nh]=make_pair(B[i],&B[i]);
	sort(Ns+1,Ns+Nh+1);for(i=1;i<=Nh;i++) *Ns[i].se=i;
	Ct=2*n;
	/*for(i=1;i<=Nh;i++){
		Ro[i]=Ro[i-1];
		for(auto j:Id[i]) CT::qry(j.fi,i,j.se,Ro[i]),CT::add(i,j.se,Ro[i]);
	}*/
	Ro[0]=0;
	for(i=1;i<=n;i++) CT::add(B[i],i,Ro[0]);
	for(i=1;i<=n;i++) if(A[i]^B[i]) CT::qry(A[i],B[i]-1,i,Ro[0]);
	while(m--){
		int x,y;scanf("%d%d",&x,&y);
		con(x+n,y);con(y+n,x);
	}
	Tarjan::BD();
	for(i=1;i<=n;i++) if(scc[i]==scc[i+n]){puts("NO");return;}
	puts("YES");
}
int main(){
	int t;
	scanf("%d",&t);
	// t=1;                                                                                       
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 16ms
memory: 208788kb

input:

2
3 1
1 5
2 7
10 11
2 1
3 3
1 5
2 7
5 7
1 2
2 3
3 1

output:

YES
YES

result:

wrong answer 2nd lines differ - expected: 'NO', found: 'YES'