oj.uz

Submission #966765

# Submission time Handle Problem Language Result Execution time Memory
966765 2024-04-20T10:13:21 Z LOLOLO Jail (JOI22_jail) C++17
49 / 100
 5000 ms 318452 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define           f    first
#define           s    second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 1.25e5;
vector <int> ed[N], ed2[N * 40];
int in[N], ou[N], dfstimer = 1, p[N][20], vi[N][20], vo[N][20], dep[N], st[N], en[N], cnt = 0;
char used[N * 40];

bool check_cycle(int u) {
    if (used[u] == 1)
        return 0;

    used[u] = 1; 
    for (auto x : ed2[u]) {
        if (used[x] != 2 && !check_cycle(x))
            return 0;
    }

    used[u] = 2;
    return 1;
}

void dfs(int u, int v) {
    vi[u][0] = ++cnt;
    vo[u][0] = ++cnt;
    if (st[u]) {
        ed2[st[u]].pb(vo[u][0]);
    }

    if (en[u]) {
        ed2[vi[u][0]].pb(en[u]);
    }

    dep[u] = dep[v] + 1;
    p[u][0] = v;

    for (int i = 1; i < 20; i++) {
        p[u][i] = p[p[u][i - 1]][i - 1];
        vi[u][i] = ++cnt;
        vo[u][i] = ++cnt;
        ed2[vo[u][i - 1]].pb(vo[u][i]);
        ed2[vo[p[u][i - 1]][i - 1]].pb(vo[u][i]);
        ed2[vi[u][i]].pb(vi[u][i - 1]);
        ed2[vi[u][i]].pb(vi[p[u][i - 1]][i - 1]);
    }

    ++dfstimer;
    in[u] = dfstimer;
    for (auto x : ed[u]) {
        if (x == v)
            continue;

        dfs(x, u);
    }

    ou[u] = dfstimer;
}

bool is(int a, int b) {
    return in[a] <= in[b] && ou[a] >= in[b]; 
}

int lca(int a, int b) {
    if (is(a, b))
        return a;

    if (is(b, a))
        return b;

    for (int i = 19; i >= 0; i--)
        if (is(p[a][i], b) == 0)
            a = p[a][i];

    return p[a][0];
}

int dis(int a, int b) {
    int c = lca(a, b);
    return dep[a] + dep[b] - dep[c] * 2;
}

void addedge(int a, int b, int id) {
    int k = dep[a] - dep[b] + 1;
    for (int j = 0; j < 20; j++) {
        if (k & (1 << j)) {
            ed2[id].pb(vi[a][j]);
            ed2[vo[a][j]].pb(id);
            a = p[a][j];
        }
    }
}

int find(int a, int k) {
    for (int j = 0; j < 20; j++)
        if (k & (1 << j))
            a = p[a][j];

    return a;
}

string solve() {
    int n;
    cin >> n;

    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        ed[a].pb(b);
        ed[b].pb(a);
    }

    int m;
    cin >> m;

    vector <pair <int, int>> save;

    for (int i = 1; i <= m; i++) {
        int s, t;
        cin >> s >> t;
        save.pb({s, t});
        st[s] = i, en[t] = i;
    }

    cnt = m;
    dfs(1, 1);

    int id = 0;
    for (auto x : save) {
        id++;
        int s = x.f, t = x.s;

        int a = s, b = t;
        if (dep[s] > dep[t])
            swap(s, t);

        //int c = lca(s, t);
        /*if (s == c) {
            addedge(p[t][0], find(t, dep[t] - dep[s] - 1), id);
        } else {
            addedge(p[s][0], c, id);
            addedge(p[t][0], c, id);
        }*/

        for (int i = 1; i <= n; i++) {
            if (i == a || i == b)
                continue;        

            if (dis(i, a) + dis(i, b) == dis(a, b)) {
                if (st[i]) {
                    ed2[st[i]].pb(id);
                }

                if (en[i]) {
                    ed2[id].pb(en[i]);
                }
            } 
        }

        if (en[a]) {
            ed2[id].pb(en[a]);
        }

        if (st[b]) {
            ed2[st[b]].pb(id);
        }
    }

    int is = 0;
    for (int i = 1; i <= m; i++) {
        if (used[i] == 0 && check_cycle(i) == 0) {
            is = 1;
            break;
        }
    }

    for (int i = 1; i <= n; i++) {
        ed[i].clear();
        st[i] = en[i] = dep[i] = 0;
    }

    for (int i = 1; i <= cnt; i++) {
        ed2[i].clear();
        used[i] = 0;
    }

    if (is == 0)
        return "Yes";

    return "No";
}

int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);

    int t = 1;
    cin >> t;

    while (t--) {
        //solve();
        cout << solve() << "\n";
    }

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 122448 KB Output is correct
2 Correct 32 ms 122712 KB Output is correct
3 Correct 31 ms 122444 KB Output is correct
4 Correct 54 ms 122784 KB Output is correct
5 Correct 78 ms 123216 KB Output is correct
6 Correct 34 ms 122716 KB Output is correct
7 Correct 34 ms 122936 KB Output is correct
8 Correct 38 ms 122820 KB Output is correct
9 Correct 772 ms 135524 KB Output is correct
10 Correct 1346 ms 318392 KB Output is correct
11 Correct 41 ms 122460 KB Output is correct
12 Correct 127 ms 123716 KB Output is correct
13 Execution timed out 5025 ms 318360 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 122460 KB Output is correct
2 Correct 31 ms 122460 KB Output is correct
3 Correct 33 ms 122872 KB Output is correct
4 Correct 35 ms 122712 KB Output is correct
5 Correct 38 ms 123156 KB Output is correct
6 Correct 35 ms 122716 KB Output is correct
7 Correct 38 ms 122968 KB Output is correct
8 Correct 40 ms 122664 KB Output is correct
9 Correct 34 ms 122716 KB Output is correct
10 Correct 35 ms 122716 KB Output is correct
11 Correct 35 ms 122708 KB Output is correct
12 Correct 33 ms 122716 KB Output is correct
13 Correct 33 ms 122716 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 122460 KB Output is correct
2 Correct 31 ms 122460 KB Output is correct
3 Correct 33 ms 122872 KB Output is correct
4 Correct 35 ms 122712 KB Output is correct
5 Correct 38 ms 123156 KB Output is correct
6 Correct 35 ms 122716 KB Output is correct
7 Correct 38 ms 122968 KB Output is correct
8 Correct 40 ms 122664 KB Output is correct
9 Correct 34 ms 122716 KB Output is correct
10 Correct 35 ms 122716 KB Output is correct
11 Correct 35 ms 122708 KB Output is correct
12 Correct 33 ms 122716 KB Output is correct
13 Correct 33 ms 122716 KB Output is correct
14 Correct 33 ms 122964 KB Output is correct
15 Correct 31 ms 122456 KB Output is correct
16 Correct 34 ms 122972 KB Output is correct
17 Correct 39 ms 122972 KB Output is correct
18 Correct 39 ms 122896 KB Output is correct
19 Correct 31 ms 122448 KB Output is correct
20 Correct 41 ms 122960 KB Output is correct
21 Correct 37 ms 122708 KB Output is correct
22 Correct 41 ms 122704 KB Output is correct
23 Correct 31 ms 122492 KB Output is correct
24 Correct 32 ms 122456 KB Output is correct
25 Correct 41 ms 122896 KB Output is correct
26 Correct 33 ms 122856 KB Output is correct
27 Correct 42 ms 122712 KB Output is correct
28 Correct 32 ms 122376 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 122460 KB Output is correct
2 Correct 31 ms 122460 KB Output is correct
3 Correct 33 ms 122872 KB Output is correct
4 Correct 35 ms 122712 KB Output is correct
5 Correct 38 ms 123156 KB Output is correct
6 Correct 35 ms 122716 KB Output is correct
7 Correct 38 ms 122968 KB Output is correct
8 Correct 40 ms 122664 KB Output is correct
9 Correct 34 ms 122716 KB Output is correct
10 Correct 35 ms 122716 KB Output is correct
11 Correct 35 ms 122708 KB Output is correct
12 Correct 33 ms 122716 KB Output is correct
13 Correct 33 ms 122716 KB Output is correct
14 Correct 33 ms 122964 KB Output is correct
15 Correct 31 ms 122456 KB Output is correct
16 Correct 34 ms 122972 KB Output is correct
17 Correct 39 ms 122972 KB Output is correct
18 Correct 39 ms 122896 KB Output is correct
19 Correct 31 ms 122448 KB Output is correct
20 Correct 41 ms 122960 KB Output is correct
21 Correct 37 ms 122708 KB Output is correct
22 Correct 41 ms 122704 KB Output is correct
23 Correct 31 ms 122492 KB Output is correct
24 Correct 32 ms 122456 KB Output is correct
25 Correct 41 ms 122896 KB Output is correct
26 Correct 33 ms 122856 KB Output is correct
27 Correct 42 ms 122712 KB Output is correct
28 Correct 32 ms 122376 KB Output is correct
29 Correct 37 ms 122964 KB Output is correct
30 Correct 119 ms 123012 KB Output is correct
31 Correct 84 ms 123044 KB Output is correct
32 Correct 95 ms 122836 KB Output is correct
33 Correct 54 ms 122704 KB Output is correct
34 Correct 151 ms 122716 KB Output is correct
35 Correct 132 ms 122856 KB Output is correct
36 Correct 140 ms 122704 KB Output is correct
37 Correct 94 ms 122704 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 122460 KB Output is correct
2 Correct 31 ms 122460 KB Output is correct
3 Correct 33 ms 122872 KB Output is correct
4 Correct 35 ms 122712 KB Output is correct
5 Correct 38 ms 123156 KB Output is correct
6 Correct 35 ms 122716 KB Output is correct
7 Correct 38 ms 122968 KB Output is correct
8 Correct 40 ms 122664 KB Output is correct
9 Correct 34 ms 122716 KB Output is correct
10 Correct 35 ms 122716 KB Output is correct
11 Correct 35 ms 122708 KB Output is correct
12 Correct 33 ms 122716 KB Output is correct
13 Correct 33 ms 122716 KB Output is correct
14 Correct 33 ms 122964 KB Output is correct
15 Correct 31 ms 122456 KB Output is correct
16 Correct 34 ms 122972 KB Output is correct
17 Correct 39 ms 122972 KB Output is correct
18 Correct 39 ms 122896 KB Output is correct
19 Correct 31 ms 122448 KB Output is correct
20 Correct 41 ms 122960 KB Output is correct
21 Correct 37 ms 122708 KB Output is correct
22 Correct 41 ms 122704 KB Output is correct
23 Correct 31 ms 122492 KB Output is correct
24 Correct 32 ms 122456 KB Output is correct
25 Correct 41 ms 122896 KB Output is correct
26 Correct 33 ms 122856 KB Output is correct
27 Correct 42 ms 122712 KB Output is correct
28 Correct 32 ms 122376 KB Output is correct
29 Correct 37 ms 122964 KB Output is correct
30 Correct 119 ms 123012 KB Output is correct
31 Correct 84 ms 123044 KB Output is correct
32 Correct 95 ms 122836 KB Output is correct
33 Correct 54 ms 122704 KB Output is correct
34 Correct 151 ms 122716 KB Output is correct
35 Correct 132 ms 122856 KB Output is correct
36 Correct 140 ms 122704 KB Output is correct
37 Correct 94 ms 122704 KB Output is correct
38 Correct 790 ms 135444 KB Output is correct
39 Correct 1429 ms 318452 KB Output is correct
40 Execution timed out 5026 ms 132956 KB Time limit exceeded
41 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 122480 KB Output is correct
2 Correct 46 ms 122448 KB Output is correct
3 Correct 42 ms 122388 KB Output is correct
4 Correct 44 ms 122528 KB Output is correct
5 Correct 59 ms 122456 KB Output is correct
6 Correct 42 ms 122716 KB Output is correct
7 Correct 47 ms 122716 KB Output is correct
8 Correct 35 ms 124520 KB Output is correct
9 Correct 45 ms 122632 KB Output is correct
10 Correct 39 ms 122452 KB Output is correct
11 Correct 35 ms 122748 KB Output is correct
12 Correct 129 ms 122912 KB Output is correct
13 Correct 859 ms 123544 KB Output is correct
14 Correct 1062 ms 123720 KB Output is correct
15 Correct 1016 ms 123556 KB Output is correct
16 Execution timed out 5064 ms 309428 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 122448 KB Output is correct
2 Correct 32 ms 122712 KB Output is correct
3 Correct 31 ms 122444 KB Output is correct
4 Correct 54 ms 122784 KB Output is correct
5 Correct 78 ms 123216 KB Output is correct
6 Correct 34 ms 122716 KB Output is correct
7 Correct 34 ms 122936 KB Output is correct
8 Correct 38 ms 122820 KB Output is correct
9 Correct 772 ms 135524 KB Output is correct
10 Correct 1346 ms 318392 KB Output is correct
11 Correct 41 ms 122460 KB Output is correct
12 Correct 127 ms 123716 KB Output is correct
13 Execution timed out 5025 ms 318360 KB Time limit exceeded
14 Halted 0 ms 0 KB -