Submission #994212

#	Time	Username	Problem	Language	Result	Execution time	Memory
994212		vjudge1	Jail (JOI22_jail)	C++17	49 / 100	5072 ms	494016 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<vector<int>> path(m);

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

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

        path[i] = move(cur_path);
    }

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

    for (int iter = 0; iter < m; iter++) {
        good.assign(m, true);
        in_path.assign(n, {});

        for (int i = 0; i < m; i++) {
            if (ended[i]) {
                good[i] = false;
                continue;
            }

            for (int const& v : path[i])
                in_path[v].push_back(i);
        }

        for (int i = 0; i < m; i++) {
            if (ended[i])
                continue;

            for (int const& j : in_path[start[i]])
                if (i != j)
                    good[j] = false;

            if (in_path[end[i]].size() > 1)
                good[i] = false;
        }

        int const good_i = find(good.begin(), good.end(), true) - good.begin();

        if (good_i == m)
            return false;

        ended[good_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");
}

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