QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#147525 | #6633. Exam Requirements | qzez | WA | 16ms | 208788kb | C++14 | 2.7kb | 2023-08-23 12:03:16 | 2023-08-25 01:38:08 |
Judging History
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'