Submission #1001282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001282		De3b0o	Jail (JOI22_jail)	C++14	61 / 100	5114 ms	313984 KiB

jail

#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define ppb pop_back()
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "Yes" << "\n";
#define no cout << "No" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define mod 1000000007
#define mid ((l+r)/2)
#define lc (2*x)
#define rc (2*x+1)

using namespace std;

ll n , m;
vector<ll> adj[120009];
ll S[120009] , T[120009];
ll o[120009];
vector<ll> g[120009];
ll vs;
ll vis[120009];
set<pll> seg[2000009];
ll et[250009];
ll ti[120009] , to[120009];
ll timer;
ll depth[120009];

void ett(ll x , ll p , ll de)
{
    depth[x]=de;
    et[timer]=x;
    ti[x]=timer;
    timer++;
    for(auto it : adj[x])
    {
        if(it==p)
            continue;
        ett(it,x,de+1);
    }
    et[timer]=x;
    to[x]=timer;
    timer++;
}

void ddfs(ll x)
{
    if(vis[x])
        return;
    vis[x]=1;
    vs++;
    for(auto it : g[x])
        ddfs(it);
}

void se(ll x , ll l , ll r , ll idx , ll val1 , ll val2)
{
    if(l>idx||r<idx)
        return;
    seg[x].in({val1,val2});
    if(l!=r)
    {
        se(lc,l,mid,idx,val1,val2);
        se(rc,mid+1,r,idx,val1,val2);
    }
}

pll sg(ll x , ll l , ll r , ll l1 , ll r1 , ll idx)
{
    if(l>r1||r<l1)
        return {1e18,-1};
    if(l>=l1&&r<=r1)
    {
        auto it = seg[x].lower_bound({idx,0});
        if(it!=seg[x].end())
            return *it;
        else
            return {1e18,-1};
    }
    pll le = sg(lc,l,mid,l1,r1,idx);
    pll ri = sg(rc,mid+1,r,l1,r1,idx);
    if(le.F>ri.F)
        return ri;
    else
        return le;
}

ll lca(ll u , ll v)
{
    pll x = sg(1,0,2*n-1,0,min(ti[u],ti[v]),max(ti[u],ti[v]));
    return x.S;

}

bool inpath(ll x , ll u , ll v)
{
    bool ans = 1;
    if((lca(x,u)==x||lca(x,v)==x)&&depth[x]>=depth[lca(u,v)])
        ans=0;
    return ans;
}

int main()
{
    d3
    ll t;
    cin >> t;
    while(t--)
    {
        cin >> n;
        for(int i = 0 ; 16*n>=i ; i++)
            seg[i].clear();
        for(int i = 1 ; n>=i ; i++)
            adj[i].clear();
        for(int i = 0 ; n-1>i ; i++)
        {
            ll u , v;
            cin >> u >> v;
            adj[u].pb(v);
            adj[v].pb(u);
        }
        timer=0;
        ett(1,0,0);
        for(int i = 1 ; n>=i ; i++)
        {
            se(1,0,2*n-1,ti[i],to[i],i);
        }
        cin >> m;
        for(int i = 1 ; m>=i ; i++)
        {
            cin >> S[i] >> T[i];
            g[i].clear();
            o[i]=0;
        }
        for(int i = 1 ; m>=i ; i++)
        {
            for(int j = 1 ; m>=j ; j++)
            {
                if(i==j)
                    continue;
                //cout << inpath(S[j],S[i],T[i]) << " " << inpath(T[i],S[j],T[j]) << "\n";
                if(inpath(S[j],S[i],T[i])&&inpath(T[i],S[j],T[j]))
                {
                    g[j].pb(i);
                    o[i]++;
                }
            }
        }
        ll x = 0;
        ll v[120009] = {0};
        while(true)
        {
            ll y = 0;
            vector<ll> d;
            for(int i = 1 ; m>=i ; i++)
            {
                if(v[i])
                    continue;
                if(o[i]==m-x-1)
                {
                    v[i]=1;
                    d.pb(i);
                    y++;
                }
            }
            if(!y)
                break;
            x+=y;
            for(auto it : d)
            {
                for(auto it1 : g[it])
                    o[it1]--;
            }
        }
        if(x==m)
            yes
        else
            no
    }
}

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