Submission #1246608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246608		damoon	Jail (JOI22_jail)	C++20	100 / 100	1095 ms	182368 KiB

jail

#include <bits/stdc++.h>
using namespace std;

//#pragma GCC optimize("O3,unroll-loops") //main
//#pragma GCC target("avx2") //cf...
//#pragma GCC target("sse4") //Quera

#define ll long long
typedef pair<int,int> pii;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef pair<pii,pii> ppp;
#define f first
#define s second

#define lc 2*id
#define rc 2*id+1
#define mid (l+r)/2
#define all(x) x.begin(),x.end()

#define pb push_back
#define pp pop_back
#define unicorn(x) x.resize(unique(x.begin(),x.end())-x.begin())
#define dig(x,d) ((x&(1ll<<d)) > 0)

string pr(int* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i]<<" ";return "";}
string pr( ll* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i]<<" ";return "";}
string pr(vector<int> vv){for(auto i:vv)cout<<i<<" ";return "";}
string pr( vector<ll> vv){for(auto i:vv)cout<<i<<" ";return "";}
string pr(pii* vv,int l,int r){for(int i=l;i<r;i++)cout<<"( "<<vv[i].f<<","<<vv[i].s<<" )    ";return "";}
string pr(vector<pii> vv){for(auto i:vv)cout<<"( "<<i.f<<","<<i.s<<" )    ";return "";}
string pr(bool* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i];return"";}
ostream& operator <<(ostream& out, pii x){out << "("<<x.f<<", "<<x.s<<") ";return out;}

const int L=2e5+10, lg=20;
const int inf=1e9+10;
int n,m;
bool mark[L];
vector<int> adj[L],P[L],tp;
int par[L][lg],h[L],st[L],fn[L],tr[L],tim;
int ind[L],F[L],S[L];

struct sagi{
    int mx[L*4];
    void reset(){
        fill(mx+1,mx+(n+1)*4,0);
    }

    void update(int id,int l,int r,int ind,int x){
        if(l+1 == r){
            mx[id] = x;
            return;
        }
        if(ind < mid)
            update(lc,l,mid,ind,x);
        else
            update(rc,mid,r,ind,x);
        mx[id] = max(mx[lc],mx[rc]);
    }

    int B(int id,int l,int r,int x){
        if(mx[id] <= x)
            return 0;
        if(l+1 == r)
            return l;
        if(mx[rc] > x)
            return B(rc,mid,r,x);
        else
            return B(lc,l,mid,x);
    }

    int F(int id,int l,int r,int l2,int r2,int x){
        if(l2 >= r2) return 0;
        if(l==l2 and r==r2)
            return B(id,l,r,x);
        int lr=0,rr=0;
        if(r2 > mid)
            rr = F(rc,mid,r,max(l2,mid),r2,x);
        if(rr) return rr;
        if(l2 < mid)
            lr = F(lc,l,mid,l2,min(r2,mid),x);
        return lr;
    }

    string prr(int id,int l,int r){
        if(l+1 == r){
            cout<<mx[id]<<" ";
            return"";
        }
        prr(lc,l,mid);
        prr(rc,mid,r);
        return "";
    }
}segp;

struct sagim{
    struct node{
        pii mn,mx;
        set<pii> av;
        node(){
            mn = pii(inf,0);
            mx = pii(0,0);
        }
    }t[L<<2];
    void reset(){
        for(int i=1;i<(n+1)*4;i++){
            t[i].mn = pii(inf,0);
            t[i].mx = pii(0,0);
            t[i].av.clear();
        }
    }
    node merge(node a,node b){
        node ans;
        ans.mn = min(a.mn, b.mn);
        ans.mx = max(a.mx, b.mx);
        return ans;
    }

    void update(int id,int l,int r,int ind,pii x,bool rem){
        if(l+1 == r){
            if(rem)
                t[id].av.erase(x);
            else
                t[id].av.insert(x);
            if(t[id].av.size()){
                t[id].mn = *t[id].av.begin();
                t[id].mx = *t[id].av.rbegin();
            }
            else{
                t[id].mn = pii(inf,0);
                t[id].mx = pii(0,0);
            }
            return;
        }
        if(ind < mid)
            update(lc,l,mid,ind,x,rem);
        else
            update(rc,mid,r,ind,x,rem);
        t[id] = merge(t[lc],t[rc]);
    }

    node get(int id,int l,int r,int l2,int r2){
        if(l2 >= r2){
            node ans;
            return ans;
        }
        if(l==l2 and r==r2)
            return t[id];
        node ans;
        if(l2 < mid)
            ans = merge(ans,get(lc,l,mid,l2,min(r2,mid)));
        if(r2 > mid)
            ans = merge(ans,get(rc,mid,r,max(l2,mid),r2));
        return ans;
    }

    string prr(int id,int l,int r){
        if(l+1 == r){
            cout<<t[id].mx<<" ";
            return"";
        }
        prr(lc,l,mid);
        prr(rc,mid,r);
        return "";
    }
}segb,segs;

void dfsT(int v){
    tr[tim] = v;
    st[v] = tim++;
    for(auto u:adj[v]){
        if(u != par[v][0]){
            par[u][0] = v;
            h[u] = h[v]+1;
            dfsT(u);
        }
    }
    fn[v] = tim;
}

int LCA(int u,int v){
    if(h[u] > h[v])
        swap(u,v);
    for(int i=lg-1;i>=0;i--){
        if(h[v] - (1<<i) >= h[u])
            v = par[v][i];
    }
    if(u == v)
        return u;
    for(int i=lg-1;i>=0;i--){
        if(par[u][i] != par[v][i]){
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}

void dfs(int v){
    mark[v] = 1;
    /*
    cout<<v<<"  "<<S[v]<<"  "<<F[v]<<endl;
    cout<<"segs: "<<segs.prr(1,1,n+1)<<endl;
    cout<<"segp: "<<segp.prr(1,1,n+1)<<endl;
    cout<<"mark: "<<pr(mark,1,m+1)<<endl;
    cout<<"-------------------------------"<<endl;
    */
    int lca = LCA(S[v],F[v]);
    while(true){
        int x = tr[segp.F(1,1,n+1,1,st[S[v]]+1,st[S[v]])];
        if(x == 0 or h[x] < h[lca])
            break;
        segp.update(1,1,n+1,st[x],0);
        if(!mark[ind[x]]){
            //cout<<v<<" --> "<<ind[x]<<endl;
            dfs(ind[x]);
        }
    }
    while(true){
        int x = tr[segp.F(1,1,n+1,1,st[F[v]]+1,st[F[v]])];
        if(x == 0 or h[x] < h[lca])
            break;
        segp.update(1,1,n+1,st[x],0);
        if(!mark[ind[x]]){
            //cout<<v<<" --> "<<ind[x]<<endl;
            dfs(ind[x]);
        }
    }
    while(true){
        pii x = segb.get(1,1,n+1,st[S[v]],fn[S[v]]).mn;
        if(x.f >= st[S[v]])
            break;
        //cout<<v<<" F: "<<x.s<<endl;
        segb.update(1,1,n+1,max(st[S[x.s]],st[F[x.s]]),pii(min(st[S[x.s]],st[F[x.s]]),x.s),1);
        if(!mark[x.s]){
            //cout<<v<<" --> "<<x.s<<endl;
            dfs(x.s);
        }
    }
    while(true){
        pii x = segs.get(1,1,n+1,st[S[v]],fn[S[v]]).mx;
        if(x.f < fn[S[v]])
            break;
        //cout<<v<<" F: "<<x.s<<endl;
        segs.update(1,1,n+1,min(st[S[x.s]],st[F[x.s]]),pii(max(st[S[x.s]],st[F[x.s]]),x.s),1);
        if(!mark[x.s]){
            //cout<<v<<" --> "<<x.s<<endl;
            dfs(x.s);
        }
    }

    for(auto u:P[S[v]]){
        if(!mark[u]){
            //cout<<v<<" --> "<<u<<endl;
            dfs(u);
        }
    }
    tp.pb(v);
}

void reset(){
    segp.reset();
    segs.reset();
    segb.reset();
    tp.clear();
    tim=0;
    for(int i=1;i<=n;i++){
        ind[i] = mark[i] = 0;
        P[i].clear();
        adj[i].clear();
    }
}

int main(){
    //ofstream cout ("out.out");
    //ifstream cin ("in2.in");

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t=1;
    cin>>t;
    for(int gg=0;gg<t;gg++){
        cin>>n;
        reset();
        for(int i=1;i<n;i++){
            int u,v;
            cin>>u>>v;
            adj[u].pb(v);
            adj[v].pb(u);
        }
        h[0] = -1;
        par[1][0] = h[1] = 0;
        tim=1;
        dfsT(1);
        for(int j=1;j<lg;j++){
            for(int i=1;i<=n;i++){
                par[i][j] = par[par[i][j-1]][j-1];
            }
        }

        cin>>m;
        for(int i=1;i<=m;i++){
            cin>>S[i]>>F[i];
            ind[F[i]] = i;
            P[LCA(S[i],F[i])].pb(i);
            segp.update(1,1,n+1,st[F[i]],fn[F[i]]);
            segs.update(1,1,n+1,min(st[F[i]],st[S[i]]),pii(max(st[F[i]],st[S[i]]),i),0);
            segb.update(1,1,n+1,max(st[F[i]],st[S[i]]),pii(min(st[F[i]],st[S[i]]),i),0);
        }

        for(int i=1;i<=m;i++){
            if(!mark[i]){
                dfs(i);
            }
        }
        reverse(all(tp));

        if(tp.size() != m){
            while(true){
                int x = 1;
            }
        }

        segp.reset();
        for(int i=1;i<=m;i++){
            segp.update(1,1,n+1,st[S[i]],fn[S[i]]);
        }

        bool ok = true;
        for(auto i:tp){
            int lca = LCA(S[i],F[i]);
            //cout<<"lca: "<<lca<<endl;

            segp.update(1,1,n+1,st[S[i]],0);
            int x = tr[segp.F(1,1,n+1,1,st[S[i]]+1,st[S[i]])];
            if(x != 0 and h[x] >= h[lca]){
                //cout<<i<<"  "<<x<<"  bads "<<endl;
                ok = false;
                break;
            }
            x = tr[segp.F(1,1,n+1,1,st[F[i]]+1,st[F[i]])];
            if(x != 0 and h[x] >= h[lca]){
                //cout<<i<<"  "<<x<<"  badf "<<endl;
                ok = false;
                break;
            }
            segp.update(1,1,n+1,st[F[i]],fn[F[i]]);
            //cout<<"segp: "<<segp.prr(1,1,n+1)<<endl;
        }

        if(ok)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
        /*
        cout<<"tr: "<<pr(tr,1,n+1)<<endl;
        cout<<"st: "<<pr(st,1,n+1)<<endl;
        cout<<"fn: "<<pr(fn,1,n+1)<<endl;
        cout<<"tp: "<<pr(tp)<<endl;
        */
    }
}

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