QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#147471#6633. Exam Requirementsqzez#WA 344ms331752kbC++142.6kb2023-08-23 10:19:042023-08-25 01:32:28

Judging History

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

  • [2023-08-25 01:32:28]
  • 评测
  • 测评结果:WA
  • 用时:344ms
  • 内存:331752kb
  • [2023-08-23 10:19:04]
  • 提交

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*20+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],Ns[N],Nh;
vector<pii> Id[N];
vector<int> S[M];
int Ct,SCC;
void con(int x,int y){S[x].emplace_back(y);}
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;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){
		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]=A[i],Ns[++Nh]=B[i];
	sort(Ns+1,Ns+Nh+1);Nh=unique(Ns+1,Ns+Nh+1)-Ns-1;
	for(i=1;i<=n;i++) A[i]=LB(Ns+1,Ns+Nh+1,A[i])-Ns,B[i]=LB(Ns+1,Ns+Nh+1,B[i])-Ns,Id[B[i]].emplace_back(A[i],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]);
	}
	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';
}

详细

Test #1:

score: 100
Accepted
time: 15ms
memory: 114508kb

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
NO

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 344ms
memory: 329408kb

input:

1
100000 100000
15084647 15220430
217541056 217598054
222963701 223110976
71224450 71340221
320463268 320631387
334861459 334924668
328950591 329083669
178996498 178996584
428529461 428605033
405428435 405504132
197936687 197947412
9058562 9190197
169407597 169474101
297518153 297590927
31471874 316...

output:

NO

result:

ok single line: 'NO'

Test #3:

score: -100
Wrong Answer
time: 342ms
memory: 331752kb

input:

1
100000 100000
14748507 14846251
125029948 125054609
463293218 463377641
198157217 198174486
61816219 61983451
43817835 43922214
146858750 146954988
30320405 30474901
19982332 20115324
118096811 118227915
446543803 446714206
334272499 334330640
334038396 334098710
142811467 142826092
343928730 3441...

output:

NO

result:

wrong answer 1st lines differ - expected: 'YES', found: 'NO'