Submission #892770

#	Time	Username	Problem	Language	Result	Execution time	Memory
892770		juliany2	Jail (JOI22_jail)	C++17	0 / 100	10 ms	10844 KiB

jail

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

template<class T> struct LZ_ST {
    static constexpr T ID = {(int) 1e9, 0};
    const int LZ_ID = 0; // or whatever ID
    inline T comb(T a, T b) { return min(a, b); } // or whatever function
 
    int sz;
    vector<T> t; 
    vector<int> lz;
 
    void init(int _sz, T val = ID) {
        sz = _sz;
        t.assign(sz * 4, val);
        lz.assign(sz * 4, LZ_ID);
    }
    void init(vector<T> &a) {
        sz = a.size();
        t.resize(sz * 4);
        lz.assign(sz * 4, LZ_ID);
 
        build(0, sz - 1, 1, a);
    }
    void build(int l, int r, int v, vector<T> &a) {
        if (l == r)
            t[v] = a[l];
        else {
            int m = l + r >> 1;
            build(l, m, v * 2, a);
            build(m + 1, r, v * 2 + 1, a);
            t[v] = comb(t[v * 2], t[v * 2 + 1]);
        }
    }
    inline void push(int l, int r, int v) {
        if (lz[v] != LZ_ID && l != r) { // might have to change
            int m = l + r >> 1;
            //change if set (=) or adding(+=) on range
            t[v * 2][0] += lz[v];
            t[v * 2 + 1][0] += lz[v];
            lz[v * 2] += lz[v];
            lz[v * 2 + 1] += lz[v];
        }
        lz[v] = LZ_ID;
    }
    void upd(int ql, int qr, int x, int l, int r, int v) {
        if (qr < l || ql > r) return;
        if (l >= ql && r <= qr) // might have to change, same as above
            t[v][0] += x, lz[v] += x;
        else {
            push(l, r, v);
            int m = l + r >> 1;
            upd(ql, qr, x, l, m, v * 2);
            upd(ql, qr, x, m + 1, r, v * 2 + 1);
            t[v] = comb(t[v * 2], t[v * 2 + 1]);
        }
    }
    void upd(int ql, int qr, int x) {
        return upd(ql, qr, x, 0, sz - 1, 1);
    }
    T query(int ql, int qr, int l, int r, int v) {
        if (qr < l || ql > r) return ID;
        if (l >= ql && r <= qr) return t[v];
        push(l, r, v);
        int m = l + r >> 1;
        return comb(query(ql, qr, l, m, v * 2), query(ql, qr, m + 1, r, v * 2 + 1));
    }
    T query(int ql, int qr) {
        return query(ql, qr, 0, sz - 1, 1);
    }
};

const int N = 2e5 + 7;
int n, m;
vector<int> adj[N];
int s[N], t[N], sz[N], head[N], pt[N], dep[N], pos[N], timer;
LZ_ST<array<int, 2>> st;
queue<int> q;

void dfs_sz(int v = 1, int p = 0) {
    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]);
        }
    }
}

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 process(int a, int b, int op) {
    if (op == 1)
        st.upd(a, b, 1);
    else {
        st.upd(a, b, -1);
        while (st.query(a, b)[0] == 1) {
            int x = st.query(a, b)[1];
            st.upd(pos[t[x]], pos[t[x]], 1e9);
            q.push(x);
        }
    }
}

void query(int a, int b, int op) {
    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], op);
    }

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

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

void solve() {
    cin >> n;

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

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

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

    cin >> m;

    vector<array<int, 2>> l(n + 1, {(int) 1e9, 0});

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

    st.init(l);

    for (int i = 1; i <= m; i++)
        query(s[i], t[i], 1);

    for (int i = 1; i <= m; i++) {
        if (st.query(pos[t[i]], pos[t[i]])[0] == 1) {
            st.upd(pos[t[i]], pos[t[i]], 1e9);
            q.push(i);
        }
    }

    int cnt = 0;
    while (q.size()) {
        int i = q.front();
        q.pop();

        query(s[i], t[i], -1);
        cnt++;
    }

    cout << (cnt == m ? "Yes" : "No") << '\n';
}

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

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

    return 0;
}

Compilation message (stderr)

jail.cpp: In instantiation of 'void LZ_ST<T>::upd(int, int, int, int, int, int) [with T = std::array<int, 2>]':
jail.cpp:61:19:   required from 'void LZ_ST<T>::upd(int, int, int) [with T = std::array<int, 2>]'
jail.cpp:108:23:   required from here
jail.cpp:54:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |             int m = l + r >> 1;
      |                     ~~^~~
jail.cpp: In instantiation of 'T LZ_ST<T>::query(int, int, int, int, int) [with T = std::array<int, 2>]':
jail.cpp:71:21:   required from 'T LZ_ST<T>::query(int, int) [with T = std::array<int, 2>]'
jail.cpp:111:29:   required from here
jail.cpp:67:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |         int m = l + r >> 1;
      |                 ~~^~~
jail.cpp: In instantiation of 'void LZ_ST<T>::build(int, int, int, std::vector<_Tp>&) [with T = std::array<int, 2>]':
jail.cpp:25:9:   required from 'void LZ_ST<T>::init(std::vector<_Tp>&) [with T = std::array<int, 2>]'
jail.cpp:162:14:   required from here
jail.cpp:31:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |             int m = l + r >> 1;
      |                     ~~^~~
jail.cpp: In instantiation of 'void LZ_ST<T>::push(int, int, int) [with T = std::array<int, 2>]':
jail.cpp:53:13:   required from 'void LZ_ST<T>::upd(int, int, int, int, int, int) [with T = std::array<int, 2>]'
jail.cpp:61:19:   required from 'void LZ_ST<T>::upd(int, int, int) [with T = std::array<int, 2>]'
jail.cpp:108:23:   required from here
jail.cpp:39:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |             int m = l + r >> 1;
      |                     ~~^~~
jail.cpp:39:17: warning: unused variable 'm' [-Wunused-variable]
   39 |             int m = l + r >> 1;
      |                 ^

• 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