Submission #1263653

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263653		inkvizytor	Jail (JOI22_jail)	C++20	100 / 100	1095 ms	163636 KiB

jail

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

#define ll long long

const ll N = 1e6 + 5;

vector<ll> v[N],g[N];
ll n,m,depth[N],vis[N],S[N],T[N],tin[N],ti,par[N],sub[N],tail[N],p[N],inv[N],xd[N],ptr;
array<ll,2> ar[N];
bool ok = 1;

inline void Add_Edge(ll a,ll b){
    if(a != b) g[a].push_back(b);
}

void dfs(ll c,ll p){
    par[c] = p;
    for(ll x : v[c]){
        if(x == p) continue;
        depth[x] = depth[c] + 1;
        dfs(x, c);
    }
}

void Prep(ll c,ll p){
    sub[c] = 1;
    for(ll x : v[c]){
        if(x == p) continue;
        Prep(x, c);
        sub[c] += sub[x];
    }
}

void HLD(ll c,ll p,ll h){
    tail[c] = h, xd[c] = ti;
    tin[ti++] = c;
    ll ne = -1;

    for(ll u : v[c]){
        if(u == p) continue;
        if(ne == -1 || sub[u] > sub[ne]) ne = u;
    }

    if(ne != -1) HLD(ne, c, h);

    for(ll u : v[c]){
        if(u == p || u == ne) continue;
        HLD(u, c, u);
    }
}

void Create(ll rt,ll l,ll r){
    p[rt] = ++ptr;
    if(l == r){
        if(S[tin[l]] != -1){
            Add_Edge(p[rt], S[tin[l]]);
        }
        return;
    }

    ll mid = (l + r) / 2;
    Create(rt * 2, l, mid), Create(rt * 2 + 1, mid + 1, r);

    Add_Edge(p[rt], p[rt * 2]);
    Add_Edge(p[rt], p[rt * 2 + 1]);
}

void Create2(ll rt,ll l,ll r){
    inv[rt] = ++ptr;
    if(l == r){
        if(T[tin[l]] != -1){
            Add_Edge(T[tin[l]], inv[rt]);
        }
        return;
    }

    ll mid = (l + r) / 2;
    Create2(rt * 2, l, mid), Create2(rt * 2 + 1, mid + 1, r);

    Add_Edge(inv[rt * 2], inv[rt]);
    Add_Edge(inv[rt * 2 + 1], inv[rt]);
}

void Add(ll rt,ll l,ll r,ll gl,ll gr,ll nd,bool gg){
    if(r < gl || l > gr) return;
    if(l >= gl && r <= gr){
        if(gg){
          Add_Edge(nd, p[rt]);
        }
        else{
            Add_Edge(inv[rt], nd);
        }
        return;
    }
    ll mid = (l + r) / 2;
    Add(rt * 2, l, mid, gl, gr, nd, gg), Add(rt * 2 + 1, mid + 1, r, gl, gr, nd, gg);
}

void Find(ll c){
    if(vis[c] == 2 || !ok) return;
    if(vis[c] == 1){
        ok = 0;
        return;
    }
    vis[c] = 1;
    for(ll u : g[c]) Find(u); 
    vis[c] = 2;
}

inline void Hm(ll l,ll r,ll nd){
    ll ln = xd[ar[nd][0]];
    if(ln >= l && ln <= r){
        if(l < ln) Add(1,1,n,l,ln-1,nd,1);
        if(ln < r) Add(1,1,n,ln+1,r,nd,1);
    }
    else Add(1,1,n,l,r,nd,1);
 
    ln = xd[ar[nd][1]];
    if(ln >= l && ln <= r){
        if(l < ln) Add(1,1,n,l,ln-1,nd,0);
        if(ln < r) Add(1,1,n,ln+1,r,nd,0);
    }
    else Add(1,1,n,l,r,nd,0);
}

void Solve(){
    cin >> n;
    ok = ti = 1;
  
    for(ll i=0;i<=min(N-1,8*n);i++){
  	    vis[i] = sub[i] = 0;
  	    v[i].clear(),g[i].clear();
  	    S[i] = T[i] = -1;
    }

    for(ll i=1;i<n;i++){
  	    ll a,b;
  	    cin >> a >> b;
  	    v[a].push_back(b);
  	    v[b].push_back(a);
    }

    dfs(1, 1);
    Prep(1, 1);
    HLD(1, 1, 1);
  
    cin >> m;
    ptr = m;

    for(ll i=1;i<=m;i++){
  	    cin >> ar[i][0] >> ar[i][1];
  	    S[ar[i][0]] = i;
  	    T[ar[i][1]] = i;
    }

    Create(1, 1, n);
    Create2(1, 1, n);

    for(ll i=1;i<=m;i++){
        ll a = ar[i][0], b = ar[i][1];
        for(;tail[a]!=tail[b]; b = par[tail[b]]){
            if(depth[tail[a]] > depth[tail[b]]) swap(a, b);
            Hm(xd[tail[b]], xd[b], i);
        }
        if(depth[a] > depth[b]) swap(a, b);
        Hm(xd[a], xd[b], i);
    }

    for(ll i=1;i<=ptr;i++){
        sort(g[i].begin(), g[i].end());
        g[i].erase(unique(g[i].begin(), g[i].end()),g[i].end());
    }

    for(ll i=1;i<=ptr;i++) Find(i);
  
  
    if(ok) cout << "Yes\n";
    else cout << "No\n";
}

int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    ll q=1;
    cin >> q;
    for (int i = 0; i < q; i++) {
        Solve();
    }
    return 0;
}

• 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