Submission #893229

#	Time	Username	Problem	Language	Result	Execution time	Memory
893229		juliany2	Jail (JOI22_jail)	C++17	0 / 100	14 ms	20128 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], sz[N], head[N], pt[N], dep[N], pos[N], S[N], tin[N], tout[N], timer;
int vis[N];
int lift[N][L];
vector<array<int, 2>> h[N];
ST<array<int, 2>> st;
set<int> p;
bool ok;

void dfs_sz(int v = 1, int p = 0) {
    tin[v] = ++timer;
    lift[v][0] = p;
    for (int i = 1; i < L; i++)
        lift[v][i] = lift[lift[v][i - 1]][i - 1];

    pt[v] = p;
    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;
}

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) {
    while (p.lower_bound(a) != p.end()) {
        int i = *p.lower_bound(a);
        if (i <= b) {
            dfs(S[i]);
            if (p.count(i))
                p.erase(i);
        }
        else
            break;
    }
}

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

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

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

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

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

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

    h[x].push_back({dep[l], i});
    h[y].push_back({dep[l], 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 (h[s[i]].back()[1] == i) {
            h[s[i]].pop_back();
            if (h[s[i]].size())
                st.upd(s[i], h[s[i]].back());
            else
                st.upd(s[i], {(int) 1e9, 0});
        }
        if (h[t[i]].back()[1] == i) {
            h[t[i]].pop_back();
            if (h[t[i]].size())
                st.upd(t[i], h[t[i]].back());
            else
                st.upd(t[i], {(int) 1e9, 0});
        }

        if (i != idx)
            dfs(i);
    }
}

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

    vis[v] = 1;

    if (p.count(pos[s[v]]))
        p.erase(pos[s[v]]);

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

    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);
    }

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

    cin >> m;

    for (int i = 1; i <= m; i++) {
        cin >> s[i] >> t[i];
        add(s[i], t[i], i);
    }

    st.init(n + 1);
    for (int i = 1; i <= n; i++) {
        sort(all(h[i]), greater<>());
        if (h[i].size())
            st.upd(i, h[i].back());
    }

    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