Submission #893306

#	Time	Username	Problem	Language	Result	Execution time	Memory
893306		juliany2	Jail (JOI22_jail)	C++17	0 / 100	21 ms	46932 KiB

jail

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

template<class T> struct ST {
    static constexpr T ID = {(int) 1e9, 0}; // or whatever ID
    inline T comb(T a, T b) { return min(a, b); } // or whatever function

    int sz;
    vector<T> t;

    void init(int _sz, T val = ID) {
        t.assign((sz = _sz) * 2, ID);
    }
    void init(vector<T> &v) {
        t.resize((sz = v.size()) * 2);
        for (int i = 0; i < sz; ++i)
            t[i + sz] = v[i];
        for (int i = sz - 1; i; --i)
            t[i] = comb(t[i * 2], t[(i * 2) | 1]);
    }
    void upd(int i, T x) {
        for (t[i += sz] = x; i > 1; i >>= 1)
            t[i >> 1] = comb(t[i], t[i ^ 1]);
    }
    T query(int l, int r) {
        T ql = ID, qr = ID;
        for (l += sz, r += sz + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ql = comb(ql, t[l++]);
            if (r & 1) qr = comb(t[--r], qr);
        }
        return comb(ql, qr);
    }
};

const int N = 2e5 + 7, L = 20;
int n, m;
vector<int> adj[N];
int s[N], t[N], ps[N], pt[N], sz[N], head[N], dep[N], pos[N], l[N], S[N], tin[N], tout[N], timer;
int vis[N];
int lift[N][L];
vector<int> h[N];
ST<array<int, 2>> st;
set<int> p;
bool ok;

void dfs_sz(int v = 1, int p = 0) {
    tin[v] = timer;
    while (h[v].size()) {
        int x = h[v].back();
        h[v].pop_back();

        if (x > 0)
            ps[x] = timer;
        else
            pt[-x] = timer;
        timer++;
    }
    lift[v][0] = p;
    for (int i = 1; i < L; i++)
        lift[v][i] = lift[lift[v][i - 1]][i - 1];

    sz[v] = 1;
    for (int &u : adj[v]) {
        if (u != p) {
            dep[u] = dep[v] + 1;
            dfs_sz(u, v);
            sz[v] += sz[u];
            if (sz[u] > sz[adj[v][0]] || adj[v][0] == p)
                swap(u, adj[v][0]);
        }
    }

    tout[v] = timer - 1;
}

int lca(int u, int v) {
    if (dep[u] > dep[v])
        swap(u, v);

    for (int i = L - 1; ~i; --i)
        if (dep[v] - (1 << i) >= dep[u])
            v = lift[v][i];

    if (u == v)
        return u;

    for (int i = L - 1; ~i; --i)
        if (lift[v][i] != lift[u][i])
            v = lift[v][i], u = lift[u][i];
    return lift[u][0];
}

void dfs_hld(int v = 1, int p = 0) {
    pos[v] = timer++;
    for (int u : adj[v]) {
        if (u != p) {
            head[u] = (u == adj[v][0] ? head[v] : u);
            dfs_hld(u, v);
        }
    }
}

void dfs(int v);

void process(int a, int b, int idx) {
    while (p.lower_bound(a) != p.end()) {
        int i = *p.lower_bound(a);
        if (i <= b && ok) {
            if (S[i] == idx)
                a = i + 1;
            else
                dfs(S[i]);
        }
        else
            break;
    }
}

void query(int a, int b, int idx) {
    for (; head[a] != head[b]; b = lift[head[b]][0]) {
        if (dep[head[a]] > dep[head[b]])
            swap(a, b);

        process(pos[head[b]], pos[b], idx);
    }

    if (dep[a] > dep[b])
        swap(a, b);

    process(pos[a], pos[b], idx);
}

void add(int x, int y, int i) {
    l[i] = lca(x, y);

    S[pos[x]] = i;
    p.insert(pos[x]);

    st.upd(ps[i], {dep[l[i]], i});
    st.upd(pt[i], {dep[l[i]], i});
}

void go(int v, int idx) {
    while (st.query(tin[v], tout[v])[0] <= dep[v]) {
        int i = st.query(tin[v], tout[v])[1];

        if (i != idx && ok) {
            st.upd(ps[i], {dep[l[i]], i});
            st.upd(pt[i], {dep[l[i]], i});
            dfs(i);
        }
        else {
            st.upd(ps[i], {(int) 1e9, 0});
            st.upd(pt[i], {(int) 1e9, 0});
        }
    }
}

void dfs(int v) {
    if (!ok)
        return;

    if (vis[v] == 1) {
        ok = 0;
        return;
    }
    if (vis[v] == 2)
        return;

    add(s[v], t[v], v);

    vis[v] = 1;

    query(s[v], t[v], v);
    go(t[v], v);

    if (p.count(pos[s[v]]))
        p.erase(pos[s[v]]);
    st.upd(ps[v], {(int) 1e9, 0});
    st.upd(pt[v], {(int) 1e9, 0});
    vis[v] = 2;
}

void solve() {
    cin >> n;

    p.clear();
    for (int i = 1; i <= n; i++) {
        adj[i].clear();
        h[i].clear();
        S[i] = 0;
    }

    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;

    for (int i = 1; i <= m; i++) {
        cin >> s[i] >> t[i];
        h[s[i]].push_back(i);
        h[t[i]].push_back(-i);
    }

    timer = 1;
    head[1] = 1;
    dfs_sz();
    timer = 1;
    dfs_hld();

    st.init(n + 1);
    for (int i = 1; i <= m; i++)
        add(s[i], t[i], i);

    fill(vis + 1, vis + m + 1, 0);

    ok = 1;
    for (int i = 1; i <= m; i++)
        if (!vis[i])
            dfs(i);

    cout << (ok ? "Yes" : "No") << '\n';
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    int t;
    cin >> t;
    
    while (t--)
        solve();

    return 0;
}

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