oj.uz

Submission #710497

# Submission time Handle Problem Language Result Execution time Memory
710497 2023-03-15T09:40:53 Z becaido Jail (JOI22_jail) C++17
60 / 100
 5000 ms 263400 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof... (u) ? ", " : ""), dout (u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

// s[i] lies on path(s[j], t[j]), build an edge(i -> j)
// t[i] lies on path(s[j], t[j]), build an edge(j -> i)

#define lpos pos*2
#define rpos pos*2+1

const int SIZE = 1.2e5 + 5;
const int H = __lg(SIZE) + 1;

int n, m;
int s[SIZE], t[SIZE];
vector<int> adj[SIZE];

int dfsid, id[SIZE], to[SIZE][H + 1];
int w[SIZE], dep[SIZE], pa[SIZE], son[SIZE], tp[SIZE];

int sz, deg[6 * SIZE];
queue<int> q;
vector<int> edge[6 * SIZE];
int nid[SIZE], in[4 * SIZE], out[4 * SIZE]; // in : large to small, out : small to large

int jump(int pos, int k) {
    int cnt = 0;
    while (k) {
        if (k & 1) pos = to[pos][cnt];
        cnt++;
        k >>= 1;
    }
    return pos;
}

int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    a = jump(a, dep[a] - dep[b]);
    if (a == b) return a;
    for (int i = H; i >= 0; i--) if (to[a][i] != to[b][i]) {
        a = to[a][i];
        b = to[b][i];
    }
    return to[a][0];
}

int walk(int a, int b) {
    int c = lca(a, b);
    if (dep[a] > dep[c]) return pa[a];
    return jump(b, dep[b] - dep[a] - 1);
}

int newnode() {
    sz++;
    deg[sz] = 0;
    edge[sz].clear();
    return sz;
}

void build(int pos, int l, int r) {
    in[pos] = newnode();
    out[pos] = newnode();
    if (l == r) {
        nid[l] = pos;
        return;
    }
    int mid = (l + r) / 2;
    build(lpos, l, mid);
    build(rpos, mid + 1, r);

    edge[in[pos]].pb(in[lpos]);
    edge[in[pos]].pb(in[rpos]);
    edge[out[lpos]].pb(out[pos]);
    edge[out[rpos]].pb(out[pos]);
}

void add(int pos, int l, int r, int L, int R, int ty, int x) {
    if (l == L && r == R) {
        if (ty == 0) edge[out[pos]].pb(x);
        if (ty == 1) edge[x].pb(in[pos]);
        return;
    }
    int mid = (L + R) / 2;
    if (r <= mid) add(lpos, l, r, L, mid, ty, x);
    else if (l > mid) add(rpos, l, r, mid + 1, R, ty, x);
    else {
        add(lpos, l, mid, L, mid, ty, x);
        add(rpos, mid + 1, r, mid + 1, R, ty, x);
    }
}

void add_edge(int x, int a, int b, int ty) {
    while (tp[a] != tp[b]) {
        if (dep[tp[a]] < dep[tp[b]]) swap(a, b);
        add(1, id[tp[a]], id[a], 1, n, ty, x);
        a = pa[tp[a]];
    }
    if (dep[a] > dep[b]) swap(a, b);
    add(1, id[a], id[b], 1, n, ty, x);
}

void solve() {
    cin >> n;
    FOR (i, 1, n) {
        adj[i].clear();
        edge[i].clear();
        deg[i] = son[i] = tp[i] = 0;
    }
    FOR (i, 2, n) {
        int a, b;
        cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    cin >> m;
    FOR (i, 1, m) cin >> s[i] >> t[i];

    auto dfs = [&](auto dfs, int pos)->void {
        for (int np : adj[pos]) if (np != pa[pos]) {
            dep[np] = dep[pos] + 1;
            pa[np] = to[np][0] = pos;
            dfs(dfs, np);
            w[pos] += w[np];
            if (w[np] > w[son[pos]]) son[pos] = np;
        }
    };
    dep[1] = 1;
    dfs(dfs, 1);
    FOR (j, 1, H) FOR (i, 1, n) to[i][j] = to[to[i][j - 1]][j - 1];

    dfsid = 0;
    auto dfs2 = [&](auto dfs2, int pos)->void {
        id[pos] = ++dfsid;
        if (!tp[pos]) tp[pos] = pos;
        if (son[pos]) {
            tp[son[pos]] = tp[pos];
            dfs2(dfs2, son[pos]);
        }
        for (int np : adj[pos]) if (np != pa[pos] && np != son[pos]) dfs2(dfs2, np);
    };
    dfs2(dfs2, 1);

    sz = m;
    build(1, 1, n);
    FOR (i, 1, m) {
        edge[i].pb(out[nid[id[s[i]]]]);
        edge[in[nid[id[t[i]]]]].pb(i);
    }
    FOR (i, 1, m) {
        add_edge(i, walk(s[i], t[i]), t[i], 0);
        add_edge(i, s[i], walk(t[i], s[i]), 1);
    }

    FOR (i, 1, sz) for (int j : edge[i]) deg[j]++;
    FOR (i, 1, sz) if (!deg[i]) q.push(i);
    int cnt = 0;
    while (q.size()) {
        int pos = q.front();
        q.pop();
        cnt++;
        for (int np : edge[pos]) if (--deg[np] == 0) q.push(np);
    }
    cout << (cnt == sz ? "Yes" : "No") << '\n';
}

int main() {
    Waimai;
    int tt;
    cin >> tt;
    while (tt--) solve();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20052 KB Output is correct
2 Correct 11 ms 20052 KB Output is correct
3 Correct 11 ms 20040 KB Output is correct
4 Correct 30 ms 20464 KB Output is correct
5 Correct 53 ms 20856 KB Output is correct
6 Correct 13 ms 20208 KB Output is correct
7 Correct 14 ms 20180 KB Output is correct
8 Correct 21 ms 20436 KB Output is correct
9 Correct 2008 ms 49228 KB Output is correct
10 Execution timed out 5030 ms 262720 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20052 KB Output is correct
2 Correct 12 ms 20068 KB Output is correct
3 Correct 13 ms 20180 KB Output is correct
4 Correct 14 ms 20180 KB Output is correct
5 Correct 13 ms 20200 KB Output is correct
6 Correct 15 ms 20204 KB Output is correct
7 Correct 15 ms 20128 KB Output is correct
8 Correct 14 ms 20208 KB Output is correct
9 Correct 16 ms 20208 KB Output is correct
10 Correct 14 ms 20208 KB Output is correct
11 Correct 13 ms 20212 KB Output is correct
12 Correct 14 ms 20080 KB Output is correct
13 Correct 13 ms 20220 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20052 KB Output is correct
2 Correct 12 ms 20068 KB Output is correct
3 Correct 13 ms 20180 KB Output is correct
4 Correct 14 ms 20180 KB Output is correct
5 Correct 13 ms 20200 KB Output is correct
6 Correct 15 ms 20204 KB Output is correct
7 Correct 15 ms 20128 KB Output is correct
8 Correct 14 ms 20208 KB Output is correct
9 Correct 16 ms 20208 KB Output is correct
10 Correct 14 ms 20208 KB Output is correct
11 Correct 13 ms 20212 KB Output is correct
12 Correct 14 ms 20080 KB Output is correct
13 Correct 13 ms 20220 KB Output is correct
14 Correct 13 ms 20036 KB Output is correct
15 Correct 12 ms 20068 KB Output is correct
16 Correct 16 ms 20260 KB Output is correct
17 Correct 14 ms 20180 KB Output is correct
18 Correct 15 ms 20180 KB Output is correct
19 Correct 12 ms 20160 KB Output is correct
20 Correct 14 ms 20212 KB Output is correct
21 Correct 13 ms 20228 KB Output is correct
22 Correct 14 ms 20208 KB Output is correct
23 Correct 12 ms 20052 KB Output is correct
24 Correct 12 ms 20180 KB Output is correct
25 Correct 14 ms 20232 KB Output is correct
26 Correct 13 ms 20180 KB Output is correct
27 Correct 13 ms 20180 KB Output is correct
28 Correct 12 ms 20140 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20052 KB Output is correct
2 Correct 12 ms 20068 KB Output is correct
3 Correct 13 ms 20180 KB Output is correct
4 Correct 14 ms 20180 KB Output is correct
5 Correct 13 ms 20200 KB Output is correct
6 Correct 15 ms 20204 KB Output is correct
7 Correct 15 ms 20128 KB Output is correct
8 Correct 14 ms 20208 KB Output is correct
9 Correct 16 ms 20208 KB Output is correct
10 Correct 14 ms 20208 KB Output is correct
11 Correct 13 ms 20212 KB Output is correct
12 Correct 14 ms 20080 KB Output is correct
13 Correct 13 ms 20220 KB Output is correct
14 Correct 13 ms 20036 KB Output is correct
15 Correct 12 ms 20068 KB Output is correct
16 Correct 16 ms 20260 KB Output is correct
17 Correct 14 ms 20180 KB Output is correct
18 Correct 15 ms 20180 KB Output is correct
19 Correct 12 ms 20160 KB Output is correct
20 Correct 14 ms 20212 KB Output is correct
21 Correct 13 ms 20228 KB Output is correct
22 Correct 14 ms 20208 KB Output is correct
23 Correct 12 ms 20052 KB Output is correct
24 Correct 12 ms 20180 KB Output is correct
25 Correct 14 ms 20232 KB Output is correct
26 Correct 13 ms 20180 KB Output is correct
27 Correct 13 ms 20180 KB Output is correct
28 Correct 12 ms 20140 KB Output is correct
29 Correct 22 ms 20464 KB Output is correct
30 Correct 17 ms 20264 KB Output is correct
31 Correct 18 ms 20308 KB Output is correct
32 Correct 18 ms 20216 KB Output is correct
33 Correct 13 ms 20216 KB Output is correct
34 Correct 15 ms 20180 KB Output is correct
35 Correct 23 ms 20288 KB Output is correct
36 Correct 16 ms 20180 KB Output is correct
37 Correct 14 ms 20196 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20052 KB Output is correct
2 Correct 12 ms 20068 KB Output is correct
3 Correct 13 ms 20180 KB Output is correct
4 Correct 14 ms 20180 KB Output is correct
5 Correct 13 ms 20200 KB Output is correct
6 Correct 15 ms 20204 KB Output is correct
7 Correct 15 ms 20128 KB Output is correct
8 Correct 14 ms 20208 KB Output is correct
9 Correct 16 ms 20208 KB Output is correct
10 Correct 14 ms 20208 KB Output is correct
11 Correct 13 ms 20212 KB Output is correct
12 Correct 14 ms 20080 KB Output is correct
13 Correct 13 ms 20220 KB Output is correct
14 Correct 13 ms 20036 KB Output is correct
15 Correct 12 ms 20068 KB Output is correct
16 Correct 16 ms 20260 KB Output is correct
17 Correct 14 ms 20180 KB Output is correct
18 Correct 15 ms 20180 KB Output is correct
19 Correct 12 ms 20160 KB Output is correct
20 Correct 14 ms 20212 KB Output is correct
21 Correct 13 ms 20228 KB Output is correct
22 Correct 14 ms 20208 KB Output is correct
23 Correct 12 ms 20052 KB Output is correct
24 Correct 12 ms 20180 KB Output is correct
25 Correct 14 ms 20232 KB Output is correct
26 Correct 13 ms 20180 KB Output is correct
27 Correct 13 ms 20180 KB Output is correct
28 Correct 12 ms 20140 KB Output is correct
29 Correct 22 ms 20464 KB Output is correct
30 Correct 17 ms 20264 KB Output is correct
31 Correct 18 ms 20308 KB Output is correct
32 Correct 18 ms 20216 KB Output is correct
33 Correct 13 ms 20216 KB Output is correct
34 Correct 15 ms 20180 KB Output is correct
35 Correct 23 ms 20288 KB Output is correct
36 Correct 16 ms 20180 KB Output is correct
37 Correct 14 ms 20196 KB Output is correct
38 Correct 2041 ms 49516 KB Output is correct
39 Execution timed out 5055 ms 263400 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20072 KB Output is correct
2 Correct 11 ms 20052 KB Output is correct
3 Correct 12 ms 20052 KB Output is correct
4 Correct 11 ms 20052 KB Output is correct
5 Correct 22 ms 20180 KB Output is correct
6 Correct 13 ms 20180 KB Output is correct
7 Correct 13 ms 20212 KB Output is correct
8 Correct 12 ms 20052 KB Output is correct
9 Correct 11 ms 20092 KB Output is correct
10 Correct 14 ms 20100 KB Output is correct
11 Correct 12 ms 20164 KB Output is correct
12 Correct 14 ms 20180 KB Output is correct
13 Correct 56 ms 20704 KB Output is correct
14 Correct 84 ms 21176 KB Output is correct
15 Correct 69 ms 20808 KB Output is correct
16 Correct 255 ms 55516 KB Output is correct
17 Correct 592 ms 68948 KB Output is correct
18 Correct 1034 ms 86924 KB Output is correct
19 Correct 323 ms 58556 KB Output is correct
20 Correct 313 ms 58600 KB Output is correct
21 Correct 354 ms 58700 KB Output is correct
22 Correct 599 ms 70296 KB Output is correct
23 Correct 412 ms 69596 KB Output is correct
24 Correct 446 ms 70488 KB Output is correct
25 Correct 452 ms 70884 KB Output is correct
26 Correct 456 ms 70924 KB Output is correct
27 Correct 432 ms 63316 KB Output is correct
28 Correct 350 ms 63268 KB Output is correct
29 Correct 373 ms 63332 KB Output is correct
30 Correct 351 ms 58384 KB Output is correct
31 Correct 299 ms 58200 KB Output is correct
32 Correct 323 ms 58156 KB Output is correct
33 Correct 295 ms 58092 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20052 KB Output is correct
2 Correct 11 ms 20052 KB Output is correct
3 Correct 11 ms 20040 KB Output is correct
4 Correct 30 ms 20464 KB Output is correct
5 Correct 53 ms 20856 KB Output is correct
6 Correct 13 ms 20208 KB Output is correct
7 Correct 14 ms 20180 KB Output is correct
8 Correct 21 ms 20436 KB Output is correct
9 Correct 2008 ms 49228 KB Output is correct
10 Execution timed out 5030 ms 262720 KB Time limit exceeded
11 Halted 0 ms 0 KB -