Submission #575591

#	Time	Username	Problem	Language	Result	Execution time	Memory
575591		InternetPerson10	Jail (JOI22_jail)	C++17	21 / 100	5068 ms	956 KiB

jail

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

vector<vector<int>> adj;
vector<bool> taken;
vector<vector<int>> paths;

bool dfs(int n, int tar) {
    taken[n] = true;
    if(n == tar) {
        paths.back().push_back(n);
        return true;
    }
    for(int ch : adj[n]) {
        if(taken[ch]) continue;
        if(dfs(ch, tar)) {
            paths.back().push_back(n);
            return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        adj.resize(n);
        taken.resize(n);
        for(int i = 1; i < n; i++) {
            int x, y;
            cin >> x >> y;
            x--; y--;
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
        int m;
        cin >> m;
        vector<int> perm(m);
        for(int i = 0; i < m; i++) {
            paths.push_back(vector<int>());
            int x, y;
            cin >> x >> y;
            dfs(x-1, y-1);
            for(int j = 0; j < n; j++) {
                taken[j] = false;
            }
            reverse(paths[i].begin(), paths[i].end());
            perm[i] = i;
        }
        bool ok = false;
        do {
            bool good = true;
            for(vector<int> v : paths) {
                taken[v[0]] = true;
            }
            for(int g : perm) {
                for(int i = 1; i < paths[g].size(); i++) {
                    good &= (!taken[paths[g][i]]);
                }
                taken[paths[g][0]] = false;
                taken[paths[g].back()] = true;
            }
            if(good) ok = true;
            for(int i = 0; i < n; i++) {
                taken[i] = false;
            }
        } while(next_permutation(perm.begin(), perm.end()));
        cout << (ok ? "Yes\n" : "No\n");
        adj.clear();
        paths.clear();
        taken.clear();
    }
}

Compilation message (stderr)

jail.cpp: In function 'int main()':
jail.cpp:64:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |                 for(int i = 1; i < paths[g].size(); i++) {
      |                                ~~^~~~~~~~~~~~~~~~~

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