Submission #882226

#	Time	Username	Problem	Language	Result	Execution time	Memory
882226		RaresFelix	Jail (JOI22_jail)	C++17	5 / 100	141 ms	46568 KiB

jail

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")

#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using db = long double;  // or double, if TL is tight
using str = string; 
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;

struct AINT {
    int n, len;
    vi V;
    AINT(int N) : n(N), len(4 * N), V(4 * N, -1) {}

    void update(int p, int v, int u, int s, int d) {
        if(d < p || p < s) return;
        if(s == d) {
            V[u] = v;
            return;
        }
        update(p, v, u << 1, s, (s + d) >> 1);
        update(p, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
        V[u] = max(V[u << 1], V[u << 1 | 1]);
    }

    void update(int p, int v) { update(p, v, 1, 0, n - 1); }

    int query(int l, int r, int u, int s, int d) {
        if(r < s || d < l) return -1; 
        if(l <= s && d <= r) return V[u];
        return max(query(l, r, u << 1, s, (s + d) >> 1), 
                query(l, r, u << 1 | 1, ((s + d) >> 1) + 1, d));
    }

    int query(int l, int r) { return query(l, r, 1, 0, n - 1); }
};

struct tree {
    int n, tmr = 0;
    vi par, niv;
    vector<vi> L, Anc;
    vi in, out, s, nxt;
    struct inmate {
        int s, t, id, viz;
    };
    vi sleep;
    vector<inmate> inmates;
    AINT A;

    tree(int N) : n(N), L(N), par(N), niv(N), in(N), out(N), s(N),
        nxt(N, 0), sleep(N, -1), A(2 * N) {}

    void add_edge(int u, int v){ 
        L[u].push_back(v);
        L[v].push_back(u);
    }

    void init() {
        function<void(int, int, int)> dfs = [&](int u, int p, int li) {
            par[u] = p;
            niv[u] = li;
            s[u] = 1;
            for(auto it : L[u]) 
                if(it != p) {
                    dfs(it, u, li + 1);
                    s[u] += s[it];
                }
        };
        dfs(0, -1, 0);
        function<void(int, int)> dfs2 = [&](int u, int p) {
            for(int i = 0; i < sz(L[u]); ++i) {
                if(L[u][0] == p || (L[u][i] != p && s[L[u][i]] > s[L[u][0]]))
                    swap(L[u][0], L[u][i]);
            }
            for(int i = 0; i < sz(L[u]); ++i) {
                if(L[u][i] == p) continue;
                if(i == 0) {
                    nxt[L[u][i]] = nxt[u];
                } else {
                    nxt[L[u][i]] = L[u][i];
                }
            }
            in[u] = tmr++;
            for(auto it : L[u]) 
                if(it != p)  {
                    dfs2(it, u);
                }
            out[u] = tmr;
        };
        dfs2(0, -1);
        Anc.push_back(par);
        for(int k = 1; (1 << k) <= n; ++k) {
            Anc.push_back(vector(n, -1));
            for(int i = 0; i < n; ++i)
                Anc[k][i] = Anc[k-1][i] == -1 ? -1 : Anc[k-1][Anc[k-1][i]];
        }
    }

    int lift(int u, int nr) {
        for(int k = sz(Anc) - 1; k >= 0; --k)
            if(nr & (1 << k)) u = Anc[k][u];
        return u;
    }

    int lca(int u, int v) {
        if(niv[u] > niv[v]) swap(u, v);
        v = lift(v, niv[v] - niv[u]);
        if(u == v) return u;
        for(int k = sz(Anc) - 1; k >= 0; --k) {
            if(Anc[k][u] != Anc[k][v]) {
                u = Anc[k][u];
                v = Anc[k][v];
            }
        }
        return par[u];
    }
    void add_prisoner(int s, int t, int id) {
        A.update(in[s], id);
        sleep[s] = id; /// s is the sleepchamber of id
        inmates.push_back({s, t, id, 0});
    }

    int query_lant(int u, int v) {
        if(niv[u] < niv[v]) swap(u, v);  
        //printf("  query_lant(%d, %d)\n", u, v);
        int re = -1;
        while(u != -1 && niv[u] >= niv[v]) {
            if(niv[nxt[u]] >= niv[v]) {
                re = max(re, A.query(in[nxt[u]], in[u]));
                //printf("     %d %d\n", nxt[u], u);
                u = par[nxt[u]];
            } else {
                re = max(re, A.query(in[v], in[u]));
                //printf("     %d %d\n", v, u);
                break;
            }
        } 
        //printf("     cu raspuns %d\n", re);
        return re;
    }

    int query(int u, int v) {
        //printf("  query(%d %d)\n", u, v);
        if(u == v) return -1;
        int l = lca(u, v);
        if(l == u) {
            return query_lant(lift(v, niv[v] - niv[u] - 1), v);
        }
        if(l == v) return query_lant(par[u], v);
        return max(query_lant(l, par[u]), query_lant(l, v));
    }

    bool on_chain(int u, int mid, int v) {
        if(lca(v, mid) != v) return 0;
        if(lca(u, mid) != mid) return 0;
        return 1;
    }

    bool on_path(int u, int mid, int v) {
        int l = lca(u, v);
        return on_chain(u, mid, l) || on_chain(v, mid, l); 
    }

    void dfs(int u, int id, bool &ok) {
        if(!ok) return;
        //printf("dfs(%d, %d, %d) \n", u, id, int(ok));
        if(inmates[id].viz != 0) {
            ok = 0;
            //printf("  -> aici am esuat\n");
            return;
        }
        int t = inmates[id].t;
        inmates[id].viz = 1;

        while(1) {
            if(!ok) return;
            int v = query(u, t);
            if(v != -1) {
                if(on_path(u, inmates[v].t, t)) {
                    ok = 0;
                    break;
                } 
                dfs(inmates[v].s, v, ok);
            }
            else break;
        }
        inmates[id].viz = 2;
        A.update(in[inmates[id].s], -1);
        A.update(in[inmates[id].t], id);
    }

    bool solve() {
        bool ok = 1;
        for(auto it : inmates) {
            if(it.viz == 2) continue;
            dfs(it.s, it.id, ok);
        }
        return ok;
    }
};

void solve() {
    int n;
    cin >> n;
    tree T(n);
    for(int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        T.add_edge(u, v);
    }
    T.init();
    int m;
    cin >> m;
    for(int i = 0; i < m; ++i) {
        int s, t;
        cin >> s >> t;
        --s; --t;
        T.add_prisoner(s, t, i);
    }
    int re = T.solve();

    if(re) cout << "Yes\n";
    else cout << "No\n";
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int te;
    cin >> te;
    while(te--) solve();
    return 0;
}

Compilation message (stderr)

jail.cpp: In constructor 'tree::tree(int)':
jail.cpp:49:16: warning: 'tree::L' will be initialized after [-Wreorder]
   49 |     vector<vi> L, Anc;
      |                ^
jail.cpp:48:8: warning:   'vi tree::par' [-Wreorder]
   48 |     vi par, niv;
      |        ^~~
jail.cpp:58:5: warning:   when initialized here [-Wreorder]
   58 |     tree(int N) : n(N), L(N), par(N), niv(N), in(N), out(N), s(N),
      |     ^~~~

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