Submission #892757

#	Time	Username	Problem	Language	Result	Execution time	Memory
892757		juliany2	Jail (JOI22_jail)	C++17	49 / 100	46 ms	1136 KiB

jail

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

const int N = 257;
int n, m;
vector<int> adj[N], g[N];
int s[N], t[N];
int vis[N];
bool ok;

void dfs(int v, int p, int t) {
    if (v == t)
        vis[v] = 1;

    for (int u : adj[v]) {
        if (u != p) {
            dfs(u, v, t);
            if (vis[u])
                vis[v] = 1;
        }
    }
}

void go(int v) {
    vis[v] = 1;

    for (int u : g[v]) {
        if (!vis[u])
            go(u);
        else if (vis[u] == 1)
            ok = 0;
    }

    vis[v] = 2;
}

void solve() {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        adj[i].clear();
        g[i].clear();
    }

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

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

    cin >> m;

    for (int i = 1; i <= m; i++)
        cin >> s[i] >> t[i];

    for (int i = 1; i <= m; i++) {
        memset(vis, 0, sizeof(vis));
        dfs(s[i], 0, t[i]);

        for (int j = 1; j <= m; j++) {
            if (i == j)
                continue;

            if (vis[s[j]])
                g[j].push_back(i);
            if (vis[t[j]])
                g[i].push_back(j);
        }
    }

    memset(vis, 0, sizeof(vis));
    ok = 1;

    for (int i = 1; i <= m; i++)
        if (!vis[i])
            go(i);

    cout << (ok ? "Yes" : "No") << '\n';
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    int t;
    cin >> t;
    
    while (t--)
        solve();

    return 0;
}

• 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