Submission #1165873

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165873		Hamed_Ghaffari	Jail (JOI22_jail)	C++20	100 / 100	1053 ms	302340 KiB

jail

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

#define pb push_back

const int MXN = 120005;
const int LOG = 17;
const int MXV = (MXN*LOG<<1)+MXN;

int n, m, N, par[MXN][LOG], S[MXN][LOG], T[MXN][LOG], swh[MXN], twh[MXN], si[MXN], ti[MXN];
int stt[MXN], fnt[MXN], timer, h[MXN];
vector<int> g[MXN], G[MXV];
int deg[MXV];

inline void add(int u, int v) {
    G[u].pb(v);
    deg[v]++;
}
void dfs(int v, int p=-1) {
    stt[v] = timer++;
    par[v][0] = p==-1 ? v : p;
    h[v] = p==-1 ? 0 : h[p]+1;
    S[v][0] = N++;
    if(swh[v]!=-1) add(swh[v], S[v][0]);
    T[v][0] = N++;
    if(twh[v]!=-1) add(T[v][0], twh[v]);
    for(int i=1; i<LOG; i++) {
        par[v][i] = par[par[v][i-1]][i-1];
        S[v][i] = N++;
        add(S[v][i-1], S[v][i]);
        add(S[par[v][i-1]][i-1], S[v][i]);
        T[v][i] = N++;
        add(T[v][i], T[v][i-1]);
        add(T[v][i], T[par[v][i-1]][i-1]);
    }
    for(int u : g[v])
        if(u!=p)
            dfs(u, v);
    fnt[v] = timer;
}
inline bool is_anc(int u, int v) {
    return stt[u]<=stt[v] && fnt[v]<=fnt[u];
}
inline int jump(int v, int d, int x, int t) {
    for(int i; d;) {
        i = __builtin_ctz(d);
        if(t==0) add(S[v][i], x);
        else if(t==1) add(x, T[v][i]);
        v = par[v][i];
        d ^= 1<<i;
    }
    return v;
}
inline void addp(int u, int v, int x, int t) {
    if(h[u]<h[v]) swap(u, v);
    u = jump(u, h[u]-h[v], x, t);
    if(u==v) {
        jump(u, 1, x, t);
        return;
    }
    for(int i=LOG-1; i>=0; i--)
        if(par[u][i]!=par[v][i]) {
            u = jump(u, 1<<i, x, t);
            v = jump(v, 1<<i, x, t);
        }
    jump(u, 2, x, t);
    jump(v, 1, x, t);
}

int qu[MXV], szx;

inline void clear() {
    timer=0;
    for(int i=0; i<n; i++) g[i].clear();
    for(int i=0; i<N; i++) {
        G[i].clear();
        deg[i] = 0;
    }
    N = 0;
}

void Main() {
    cin >> n;
    for(int i=0, u,v; i<n-1; i++) {
        cin >> u >> v; u--; v--;
        g[u].pb(v);
        g[v].pb(u);
    }
    cin >> m;
    fill(swh, swh+n, -1);
    fill(twh, twh+n, -1);
    for(int i=0; i<m; i++) {
        cin >> si[i] >> ti[i];
        swh[--si[i]] = twh[--ti[i]] = i;
    }
    N = m;
    dfs(0);
    for(int i=0; i<m; i++) {
        if(is_anc(si[i], ti[i])) jump(ti[i], h[ti[i]]-h[si[i]], i, 0);
        else addp(par[si[i]][0], ti[i], i, 0);
        if(is_anc(ti[i], si[i])) jump(si[i], h[si[i]]-h[ti[i]], i, 1);
        else addp(par[ti[i]][0], si[i], i, 1);
    }
    for(int i=0; i<N; i++)
        if(!deg[i])
            qu[szx++] = i;
    int cnt=0;
    while(szx) {
        cnt++;
        int v = qu[--szx];
        for(int u : G[v])
            if(!(--deg[u]))
                qu[szx++] = u;
    }
    cout << (cnt==N ? "Yes" : "No") << '\n';
    clear();
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int tc;
    cin >> tc;
    while(tc--) Main();
    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