QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#734573 | #6633. Exam Requirements | Vedant18 | WA | 168ms | 76428kb | C++23 | 4.5kb | 2024-11-11 12:51:58 | 2024-11-11 12:51:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define in(a, b) for (ll i = (a); i <= (b); i++) // in using i
#define inj(a, b) for (ll j = (a); j <= (b); j++) // in using j
#define ink(a, b) for (ll k = (a); k <= (b); k++) // in using k
#define inl(a, b) for (ll l = (a); l <= (b); l++) // in using l
#define inr(a, b) for(ll i = (a); i >= (b); i--) // in reverse
#define inrj(a, b) for(ll j = (a); j >= (b); j--) // in reverse
#define inrk(a, b) for(ll k = (a); k >= (b); k--) // in reverse
#define inrl(a, b) for(ll l = (a); l >= (b); l--) // in reverse
#define tt ll tcs; cin>>tcs; while(tcs--) // include test cases
#define ina(arr,n) ll arr[(n+1)]={0}; in(1,n) cin>>arr[i] // input arr of n elements
#define inv(vec,n) vector<ll> vec(n+1); vec[0]=0; in(1,n) cin>>vec[i]; // input vector of n elements
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pll pair <ll,ll>
#define vpll vector <pll>
#define sll set <ll>
#define vll vector<ll>
#define mll map <ll,ll>
#define all(x) x.begin(), x.end()
const ll mod=1e9+7;
#define vvll vector<vll>
#define pref(p,a,n) vll p(n+1); in(1,n) p[i]=p[i-1]+a[i];
#define vec2(a,n,m) vvll a(n+1,vll(m+1))
// #define vec2(a,n,m,val) vvll a(n+1,vll(m+1,val))
#define vec3(a,l,m,n) vector<vvll>a(l+1,vvll(m+1,vll(n+1)));
// #define vec3(a,l,m,n,val) vector<vvll>a(l+1,vvll(m+1,vll(n+1,val)));
# define FAST ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int main(){
FAST
tt{
ll n,m;cin>>n>>m;
vpll inp(n+1);
in(1,n){
cin>>inp[i].first>>inp[i].second;
}
sort(all(inp));
ll N=(1<<ll(ceil(log2(n))));
vvll adj(4*N);
for(int v=1;v<N;v++){
adj[v].push_back(2*v);
adj[v].push_back(2*v+1);
adj[2*N+(2*v)].push_back(2*N+v);
adj[2*N+2*v+1].push_back(2*N+v);
}
vll vec;
function<void(int,int,int,int,int) >find=[&](ll v, ll tl, ll tr,ll l, ll r){
if(l>r){
return ;
}
if(tl==l&&r==tr){
vec.push_back(v);
return;
}
ll tm=(tl+tr)/2;
find(2*v,tl,tm,l,min(r,tm));
find(2*v+1,tm+1,tr,max(l,tm+1),r);
};
in(1,n){
ll lo=i;
ll hi=n;
ll ans=i;
while(lo<=hi){
ll mid=(lo+hi)/2;
if(inp[mid].first<=inp[i].second){
ans=mid;
lo=mid+1;
}
else{
hi=mid-1;
}
}
//i+1...ans
find(1,1,N,i+1,ans);
for(auto x:vec){
// adj[2*N+i-1].push_back(x);
adj[3*N+i-1].push_back(x);
adj[2*N+x].push_back(N+i-1);
}
vec.clear();
}
in(1,m){
ll a,b;
cin>>a>>b;
// adj[2*N+a-1].push_back(N+b-1);
// adj[2*N+b-1].push_back(N+a-1);
adj[N+a-1].push_back(3*N+b-1);
adj[N+b-1].push_back(3*N+a-1);
}
ll NN=4*N;
vvll r_adj(NN);
in(1,NN-1){
for(auto x:adj[i]){
r_adj[x].push_back(i);
}
}
vll vis(NN);
vll ord;
function<void(int)>dfs=[&](int v){
vis[v]=1;
for(auto x:adj[v]){
if(vis[x]==0){
dfs(x);
}
}
ord.push_back(v);
};
in(1,NN-1){
if(vis[i]==0){
dfs(i);
}
}
reverse(all(ord));
// vis.assign(0,NN+1);
vis.clear();
vis.resize(NN);
ll id=1;
function<void(int)>dfs2=[&](int v){
vis[v]=id;
for(auto x:r_adj[v]){
if(vis[x]==0){
dfs2(x);
}
}
};
for(auto x:ord){
if(vis[x]==0){
dfs2(x);
id++;
}
}
bool ok=1;
in(1,n){
if(vis[3*N+i-1]==vis[N+i-1]){
ok=0;
}
}
cout<<(ok?"YES\n":"NO\n");
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3896kb
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: -100
Wrong Answer
time: 168ms
memory: 76428kb
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:
YES
result:
wrong answer 1st lines differ - expected: 'NO', found: 'YES'