Submission #994307

#	Time	Username	Problem	Language	Result	Execution time	Memory
994307		Error42	Jail (JOI22_jail)	C++17	61 / 100	5054 ms	495640 KiB

jail

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> graph;
vector<int> cur_path;

bool dfs(int const cur, int const par, int const goal) {
    if (cur == goal) {
        cur_path.push_back(cur);
        return true;
    }

    for (int const& neigh : graph[cur]) {
        if (neigh == par)
            continue;

        if (dfs(neigh, cur, goal)) {
            cur_path.push_back(cur);
            return true;
        }
    }

    return false;
}

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

    graph.assign(n, {});

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;

        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    int m;
    cin >> m;

    vector<int> start(m);
    vector<int> end(m);
    vector<int> end_of(n, -1);
    vector<vector<int>> path(m);

    for (int i = 0; i < m; i++) {
        cin >> start[i] >> end[i];
        start[i]--; end[i]--;

        end_of[end[i]] = i;

        cur_path.clear();
        dfs(start[i], -1, end[i]);

        path[i] = move(cur_path);
    }

    vector<char> ended(m);
    vector<int> violations(m);
    vector<vector<int>> in_path(n);

    for (int i = 0; i < m; i++) {
        for (int const& v : path[i])
            in_path[v].push_back(i);
    }

    for (int i = 0; i < m; i++) {
        for (int const& j : in_path[start[i]])
            violations[j]++;

        for (int const& j : in_path[end[i]])
            violations[i]++;
    }

    vector<int> available;

    for (int i = 0; i < m; i++) {
        if (violations[i] == 2)
            available.push_back(i);
    }

    for (int iter = 0; iter < m; iter++) {
        if (available.size() == 0)
            return false;

        int const i = available.back();
        available.pop_back();

        for (int const& j : in_path[start[i]]) {
            violations[j]--;
            if (violations[j] == 2)
                available.push_back(j);
        }

        for (int const& v : path[i]) {
            if (end_of[v] == -1)
                continue;

            violations[end_of[v]]--;

            if (violations[end_of[v]] == 2) {
                available.push_back(end_of[v]);
            }
        }
        
        ended[i] = true;
    }

    return true;
}

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

    int t;
    cin >> t;

    while (t--)
        cout << (solve() ? "Yes\n" : "No\n");
}

Compilation message (stderr)

jail.cpp: In function 'bool solve()':
jail.cpp:77:25: warning: unused variable 'j' [-Wunused-variable]
   77 |         for (int const& j : in_path[end[i]])
      |                         ^

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23