oj.uz

Submission #882226

# Submission time Handle Problem Language Result Execution time Memory
882226 2023-12-02T20:15:26 Z RaresFelix Jail (JOI22_jail) C++17
5 / 100
 141 ms 46568 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 11 ms 348 KB Output is correct
5 Correct 24 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 30 ms 2108 KB Output is correct
10 Correct 39 ms 35192 KB Output is correct
11 Correct 5 ms 344 KB Output is correct
12 Correct 32 ms 344 KB Output is correct
13 Correct 96 ms 36296 KB Output is correct
14 Correct 60 ms 36236 KB Output is correct
15 Correct 57 ms 36296 KB Output is correct
16 Correct 79 ms 37300 KB Output is correct
17 Correct 98 ms 36352 KB Output is correct
18 Correct 141 ms 46568 KB Output is correct
19 Correct 117 ms 36300 KB Output is correct
20 Correct 67 ms 36420 KB Output is correct
21 Correct 52 ms 36300 KB Output is correct
22 Correct 49 ms 36300 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Incorrect 1 ms 464 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Incorrect 1 ms 464 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Incorrect 1 ms 464 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Incorrect 1 ms 464 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 460 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 11 ms 348 KB Output is correct
5 Correct 24 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 30 ms 2108 KB Output is correct
10 Correct 39 ms 35192 KB Output is correct
11 Correct 5 ms 344 KB Output is correct
12 Correct 32 ms 344 KB Output is correct
13 Correct 96 ms 36296 KB Output is correct
14 Correct 60 ms 36236 KB Output is correct
15 Correct 57 ms 36296 KB Output is correct
16 Correct 79 ms 37300 KB Output is correct
17 Correct 98 ms 36352 KB Output is correct
18 Correct 141 ms 46568 KB Output is correct
19 Correct 117 ms 36300 KB Output is correct
20 Correct 67 ms 36420 KB Output is correct
21 Correct 52 ms 36300 KB Output is correct
22 Correct 49 ms 36300 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 2 ms 348 KB Output is correct
29 Correct 2 ms 348 KB Output is correct
30 Incorrect 1 ms 464 KB Output isn't correct
31 Halted 0 ms 0 KB -