Submission #712901

#	Time	Username	Problem	Language	Result	Execution time	Memory
712901		lam	Jail (JOI22_jail)	C++14	5 / 100	73 ms	13120 KiB

jail

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 2e4 + 10;
typedef pair<int,int> ii;
#define ff first
#define ss second
int n,m;
vector <int> adj[maxn];
ii a[maxn];
vector <ii> d;
int f[maxn];
void update(int x, int val)
{
    while (x>0)
    {
        f[x]+=val;
        x-=(x&-x);
    }
}
int get(int x)
{
    int temp = 0;
    while (x<=n)
    {
        temp+=f[x];
        x+=(x&-x);
    }
    return temp;
}
bool cmp(ii x, ii y)
{
    if (x.ff!=y.ff) return x.ff<y.ff;
    return x.ss>y.ss;
}
void xuly()
{
    cin>>n;
    for (int i=1; i<=n; i++) adj[i].clear();
    for (int i=1; i<n; i++)
    {
        int u,v; cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    cin>>m;
    d.clear();
    for (int i=1; i<=m; i++)
    {
        int l,r; cin>>l>>r;
        a[i]={l,r};
        if (l<=r)
        {
            d.push_back({l,1});
            d.push_back({r,-1});
        }
        else
        {
            d.push_back({l,-2});
            d.push_back({r,2});
        }
    }
    int num1,num2;
    num1=num2=0;
    bool check = 1;
    sort(d.begin(),d.end());
    for (ii i:d)
    {
        if (i.ss==1) num1++;
        else if (i.ss==-1) num1--;
        else if (i.ss==2) num2++;
        else num2--;
        if (num1>0&&num2>0)
        {
            cout<<"No\n";
            return;
        }
    }
    d.clear();
    for (int i=1; i<=m; i++)
    {
        if (a[i].ff<a[i].ss)
        {
            d.push_back({a[i].ff,a[i].ss});
            d.push_back({a[i].ss,-1});
        }
        else
        {
            d.push_back({a[i].ss,a[i].ff});
            d.push_back({a[i].ff,-1});
        }
    }
    sort(d.begin(),d.end(),cmp);
    fill_n(f,n+1,0);
    for (ii i:d)
    {
        if (i.ss==-1) update(i.ff,-1);
        else
        {
            if (get(i.ss+1)>0)
            {
                cout<<"No\n";
                return;
            }
            update(i.ss,1);
        }
    }
    cout<<"Yes\n";

}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int tt; cin>>tt;
    while (tt--) xuly();
}

Compilation message (stderr)

jail.cpp: In function 'void xuly()':
jail.cpp:64:10: warning: unused variable 'check' [-Wunused-variable]
   64 |     bool check = 1;
      |          ^~~~~

• Subtask 1: 5 / 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