제출 #955901

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
955901		YassirSalama	Jail (JOI22_jail)	C++17	0 / 100	1 ms	2396 KiB

jail

#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
#ifdef IOI
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#else
#define dbg(...) 1337;
#endif
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define int long long
const int MAXN=3e5+100;
int bit[MAXN];
void add(int i,int x){
    i++;
    while(i<MAXN){
        bit[i]+=x;
        i+=i&-i;
    }
}
int q(int i){
    int ans=0;
    i++;
    while(i){
        ans+=bit[i];
        i-=i&-i;
    }
    return ans;
}
int qq(int a,int b){
    if(b<a) swap(a,b);
    return q(b)-q(a+1);
}
int n,m;
void init(){
    for(int i=0;i<2*n;i++){
        bit[i]=0;
    }
}

void solve(){
    cin>>n;
    init();
    vector<pair<int,int>> v1,v2,v3;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
    }
    int m;
    cin>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        // dbg(a,b)
        if(a<b) v1.pb({a,b});
        else v2.pb({a,b});
    }
    sort(all(v1));
    sort(all(v2));
    // swap(v1,v2);
    int a=v1.size();
    int b=v2.size();
    for(int i=a-1;i>=0;i--){
        if(qq(v1[i].F,v1[i].S)){
            cout<<"No"<<endl;
            return;
        }
        add(v1[i].S,1);
    }
    // dbg("h")
    init();
    // dbg(b)
    for(int i=b-1;i>=0;i--){
        if(qq(v2[i].S,v2[i].F)){
            cout<<"No"<<endl;
            return;
        }
        add(v2[i].F,1);
    }
    // dbg("h")
    init();
    for(auto x:v2) add(x.F,1);
    for(auto x:v1){
        if(qq(x.F,x.S)){
            cout<<"No"<<endl;
            return;
        }
    }
    cout<<"Yes"<<endl;
    
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t--){
    solve();
}
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23