oj.uz

Submission #966318

# Submission time Handle Problem Language Result Execution time Memory
966318 2024-04-19T17:23:41 Z LOLOLO Jail (JOI22_jail) C++14
0 / 100
 928 ms 318112 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];
}

void addedge(int a, int b, int id) {
    if (is(a, b))
        return;

    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);
        }

        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] = 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 58 ms 130640 KB Output is correct
2 Correct 29 ms 130640 KB Output is correct
3 Correct 29 ms 130648 KB Output is correct
4 Correct 51 ms 131164 KB Output is correct
5 Correct 74 ms 131556 KB Output is correct
6 Correct 33 ms 130904 KB Output is correct
7 Correct 31 ms 130908 KB Output is correct
8 Correct 33 ms 131164 KB Output is correct
9 Correct 213 ms 142464 KB Output is correct
10 Correct 928 ms 318112 KB Output is correct
11 Incorrect 38 ms 130652 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 130652 KB Output is correct
2 Correct 29 ms 130388 KB Output is correct
3 Correct 31 ms 130908 KB Output is correct
4 Correct 34 ms 131020 KB Output is correct
5 Correct 30 ms 131036 KB Output is correct
6 Correct 32 ms 131160 KB Output is correct
7 Correct 31 ms 130904 KB Output is correct
8 Correct 32 ms 130900 KB Output is correct
9 Correct 32 ms 130904 KB Output is correct
10 Correct 31 ms 130896 KB Output is correct
11 Correct 31 ms 130908 KB Output is correct
12 Incorrect 30 ms 130900 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 130652 KB Output is correct
2 Correct 29 ms 130388 KB Output is correct
3 Correct 31 ms 130908 KB Output is correct
4 Correct 34 ms 131020 KB Output is correct
5 Correct 30 ms 131036 KB Output is correct
6 Correct 32 ms 131160 KB Output is correct
7 Correct 31 ms 130904 KB Output is correct
8 Correct 32 ms 130900 KB Output is correct
9 Correct 32 ms 130904 KB Output is correct
10 Correct 31 ms 130896 KB Output is correct
11 Correct 31 ms 130908 KB Output is correct
12 Incorrect 30 ms 130900 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 130652 KB Output is correct
2 Correct 29 ms 130388 KB Output is correct
3 Correct 31 ms 130908 KB Output is correct
4 Correct 34 ms 131020 KB Output is correct
5 Correct 30 ms 131036 KB Output is correct
6 Correct 32 ms 131160 KB Output is correct
7 Correct 31 ms 130904 KB Output is correct
8 Correct 32 ms 130900 KB Output is correct
9 Correct 32 ms 130904 KB Output is correct
10 Correct 31 ms 130896 KB Output is correct
11 Correct 31 ms 130908 KB Output is correct
12 Incorrect 30 ms 130900 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 130652 KB Output is correct
2 Correct 29 ms 130388 KB Output is correct
3 Correct 31 ms 130908 KB Output is correct
4 Correct 34 ms 131020 KB Output is correct
5 Correct 30 ms 131036 KB Output is correct
6 Correct 32 ms 131160 KB Output is correct
7 Correct 31 ms 130904 KB Output is correct
8 Correct 32 ms 130900 KB Output is correct
9 Correct 32 ms 130904 KB Output is correct
10 Correct 31 ms 130896 KB Output is correct
11 Correct 31 ms 130908 KB Output is correct
12 Incorrect 30 ms 130900 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 130664 KB Output is correct
2 Correct 29 ms 130652 KB Output is correct
3 Correct 31 ms 130388 KB Output is correct
4 Correct 31 ms 130652 KB Output is correct
5 Incorrect 43 ms 130900 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 130640 KB Output is correct
2 Correct 29 ms 130640 KB Output is correct
3 Correct 29 ms 130648 KB Output is correct
4 Correct 51 ms 131164 KB Output is correct
5 Correct 74 ms 131556 KB Output is correct
6 Correct 33 ms 130904 KB Output is correct
7 Correct 31 ms 130908 KB Output is correct
8 Correct 33 ms 131164 KB Output is correct
9 Correct 213 ms 142464 KB Output is correct
10 Correct 928 ms 318112 KB Output is correct
11 Incorrect 38 ms 130652 KB Output isn't correct
12 Halted 0 ms 0 KB -