oj.uz

Submission #994197

# Submission time Handle Problem Language Result Execution time Memory
994197 2024-06-07T08:39:16 Z vjudge1 Jail (JOI22_jail) C++17
0 / 100
 4693 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 120'001;

vector<int> g[MAXN], g2[MAXN];
int tin[MAXN], tout[MAXN], s[MAXN], e[MAXN], par[MAXN], col[MAXN], hv[MAXN], timer;
bool ok;

void dfs(int u, int p = -1) {
    tin[u] = timer++;
    par[u] = p;
    for (int v : g[u]) {
        if (v != p) dfs(v, u);
    }
    tout[u] = timer++;
}

void dfs2(int u, stack<int> &top) {
    col[u] = 1;
    for (int v : g2[u]) {
        if (col[v] == 0) dfs2(v, top);
        else if (col[v] == 1) ok = false;
    }
    col[u] = 2;
    top.push(u);
}

bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

void solve() {
    int n; cin >> n;
    ok = true;
    fill(s, s+n+1, 0);
    fill(e, e+n+1, 0);
    fill(col, col+n+1, 0);
    fill(hv, hv+MAXN, 0);
    timer = 1;
    for (int i = 1; i <= n; i++) {
        g[i].clear();
        g2[i].clear();
    }
    for (int i = 0; i < n-1; i++) {
        int u, v; cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    dfs(1);
    int m; cin >> m;
    vector<pair<int, int>> edges(m+1);
    for (int i = 1; i <= m; i++) {
        cin >> edges[i].first >> edges[i].second;
        auto [u, v] = edges[i];
        s[u] = e[v] = i;
        hv[edges[i].first] = i;
    }

    auto nxt = [&](int u, int v) {
        if (u == v) return -1;
        if (is_ancestor(u, v)) {
            for (int i : g[u]) {
                if (par[u] != i && is_ancestor(i, v)) {
                    return i;
                }
            }
        } else {
            return par[u];
        }
    };

    for (int i = 1; i <= m; i++) {
        auto [u, v] = edges[i];
        while (u != -1) {
            if (e[u] && e[u] != i) {
                g2[i].emplace_back(e[u]);
            }
            u = nxt(u, v);
        }
    }

    function<void(int,int)> mv = [&](int idx, int p) {
        if (!ok) return;
        int v = nxt(edges[idx].first, edges[idx].second);
        if (v == -1 || v == p) {
            ok = false;
            return;
        }
        if (hv[v]) {
            mv(hv[v], edges[idx].first);
        }
        hv[edges[idx].first] = 0;
        hv[v] = idx;
        edges[idx].first = v;
    };

    stack<int> top;
    for (int i = 1; i <= m; i++) {
        if (col[i] == 0) dfs2(i, top);
    }
    while (!top.empty() && ok) {
        int i = top.top(); top.pop();
        while (edges[i].first != edges[i].second && ok) {
            mv(i, -1);
        }
    }
    cout << (ok?"Yes\n":"No\n");
}

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

Compilation message

jail.cpp: In lambda function:
jail.cpp:73:5: warning: control reaches end of non-void function [-Wreturn-type]
   73 |     };
      |     ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9304 KB Output is correct
2 Correct 2 ms 9304 KB Output is correct
3 Correct 2 ms 9308 KB Output is correct
4 Correct 10 ms 9388 KB Output is correct
5 Correct 18 ms 9308 KB Output is correct
6 Correct 2 ms 9308 KB Output is correct
7 Correct 2 ms 9308 KB Output is correct
8 Correct 3 ms 9308 KB Output is correct
9 Correct 89 ms 10880 KB Output is correct
10 Correct 712 ms 19240 KB Output is correct
11 Correct 11 ms 9304 KB Output is correct
12 Correct 29 ms 9308 KB Output is correct
13 Correct 126 ms 34388 KB Output is correct
14 Correct 86 ms 43344 KB Output is correct
15 Runtime error 4693 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9304 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 2 ms 9396 KB Output is correct
4 Correct 2 ms 9308 KB Output is correct
5 Correct 2 ms 9308 KB Output is correct
6 Correct 2 ms 9560 KB Output is correct
7 Incorrect 2 ms 9308 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9304 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 2 ms 9396 KB Output is correct
4 Correct 2 ms 9308 KB Output is correct
5 Correct 2 ms 9308 KB Output is correct
6 Correct 2 ms 9560 KB Output is correct
7 Incorrect 2 ms 9308 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9304 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 2 ms 9396 KB Output is correct
4 Correct 2 ms 9308 KB Output is correct
5 Correct 2 ms 9308 KB Output is correct
6 Correct 2 ms 9560 KB Output is correct
7 Incorrect 2 ms 9308 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9304 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 2 ms 9396 KB Output is correct
4 Correct 2 ms 9308 KB Output is correct
5 Correct 2 ms 9308 KB Output is correct
6 Correct 2 ms 9560 KB Output is correct
7 Incorrect 2 ms 9308 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9304 KB Output is correct
2 Correct 2 ms 9304 KB Output is correct
3 Correct 2 ms 9308 KB Output is correct
4 Correct 10 ms 9388 KB Output is correct
5 Correct 18 ms 9308 KB Output is correct
6 Correct 2 ms 9308 KB Output is correct
7 Correct 2 ms 9308 KB Output is correct
8 Correct 3 ms 9308 KB Output is correct
9 Correct 89 ms 10880 KB Output is correct
10 Correct 712 ms 19240 KB Output is correct
11 Correct 11 ms 9304 KB Output is correct
12 Correct 29 ms 9308 KB Output is correct
13 Correct 126 ms 34388 KB Output is correct
14 Correct 86 ms 43344 KB Output is correct
15 Runtime error 4693 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -