oj.uz

Submission #994198

# Submission time Handle Problem Language Result Execution time Memory
994198 2024-06-07T08:40:41 Z vjudge1 Jail (JOI22_jail) C++17
0 / 100
 4701 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+n+1, 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 9052 KB Output is correct
2 Correct 1 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 7 ms 9140 KB Output is correct
5 Correct 12 ms 9048 KB Output is correct
6 Correct 2 ms 9048 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 3 ms 9052 KB Output is correct
9 Correct 90 ms 10672 KB Output is correct
10 Correct 702 ms 19300 KB Output is correct
11 Correct 4 ms 9048 KB Output is correct
12 Correct 22 ms 9236 KB Output is correct
13 Correct 128 ms 34388 KB Output is correct
14 Correct 78 ms 41436 KB Output is correct
15 Runtime error 4701 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 9048 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 2 ms 9052 KB Output is correct
6 Correct 2 ms 9048 KB Output is correct
7 Incorrect 2 ms 9048 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 9048 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 2 ms 9052 KB Output is correct
6 Correct 2 ms 9048 KB Output is correct
7 Incorrect 2 ms 9048 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 9048 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 2 ms 9052 KB Output is correct
6 Correct 2 ms 9048 KB Output is correct
7 Incorrect 2 ms 9048 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 9048 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 2 ms 9052 KB Output is correct
6 Correct 2 ms 9048 KB Output is correct
7 Incorrect 2 ms 9048 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 9052 KB Output is correct
2 Correct 1 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 1 ms 9052 KB Output is correct
5 Correct 5 ms 9052 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Incorrect 2 ms 9052 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 9052 KB Output is correct
2 Correct 1 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 7 ms 9140 KB Output is correct
5 Correct 12 ms 9048 KB Output is correct
6 Correct 2 ms 9048 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 3 ms 9052 KB Output is correct
9 Correct 90 ms 10672 KB Output is correct
10 Correct 702 ms 19300 KB Output is correct
11 Correct 4 ms 9048 KB Output is correct
12 Correct 22 ms 9236 KB Output is correct
13 Correct 128 ms 34388 KB Output is correct
14 Correct 78 ms 41436 KB Output is correct
15 Runtime error 4701 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -