QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#147488 | #6633. Exam Requirements | qzez# | WA | 566ms | 442604kb | C++14 | 2.6kb | 2023-08-23 10:53:30 | 2023-08-25 01:33:12 |
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],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: 208724kb
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: 566ms
memory: 440276kb
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: 557ms
memory: 442604kb
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'