Submission #1000220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000220		onbert	Jail (JOI22_jail)	C++17	49 / 100	5078 ms	27228 KiB

jail

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 120005, maxN = 480005, lgn = 17, INF = 1e18;
int n, m;
vector<int> ADJ[maxn], adj[maxn];
pair<int,int> a[maxn];
int sz[maxn], fa[maxn], d[maxn], newid[maxn], lim[maxn], cnter = 0;

void dfs1(int u) {
    sz[u] = 1;
    int f = -1;
    for (int v:ADJ[u]) {
        if (sz[v]) {
            f = v;
            continue;
        }
        dfs1(v);
        sz[u] += sz[v];
    }
    if (f!=-1) ADJ[u].erase(find(ADJ[u].begin(), ADJ[u].end(), f));
    // cout << u << endl;
    // for (int v:ADJ[u]) cout << v << " "; cout << endl;
    for (int j=1;j<ADJ[u].size();j++) if (sz[ADJ[u][j]] > sz[ADJ[u][0]]) swap(ADJ[u][0], ADJ[u][j]);
}
void dfs2(int u) {
    cnter++;
    newid[u] = cnter;
    for (int v:ADJ[u]) {
        d[cnter+1] = d[newid[u]] + 1;
        dfs2(v);
        fa[newid[v]] = newid[u];
    }
    lim[newid[u]] = cnter;
}

void solve() {
    cin >> n;
    for (int i=1;i<=n;i++) sz[i] = 0, adj[i].clear(), ADJ[i].clear();
    cnter = 0;
    for (int i=1;i<=n-1;i++) {
        int u, v;
        cin >> u >> v;
        ADJ[u].push_back(v);
        ADJ[v].push_back(u);
    }
    fa[1] = 0, d[1] = 0;
    dfs1(1); dfs2(1);
    bool guy[n+1];
    for (int i=1;i<=n;i++) guy[i] = 0;
    for (int i=1;i<=n;i++) a[i] = {-1, -1};
    cin >> m;
    for (int i=1;i<=m;i++) {
        int s, t;
        cin >> s >> t;
        s = newid[s], t = newid[t];
        a[t] = {s, t};
        guy[s] = true;
    }
    // for (int i=1;i<=n;i++) cout << newid[i] << " "; cout << endl;
    // for (int i=1;i<=n;i++) cout << d[i] << " "; cout << endl;
    bool yes[n+1], no[n+1];
    for (int cnt = 0; cnt < m; cnt++) {
        for (int i=1;i<=n;i++) yes[i] = (a[i].first!=-1), no[i] = 0;
        for (int i=1;i<=n;i++) {
            if (a[i].first==-1) continue;
            auto [u, v] = a[i];
            auto [s, t] = a[i];
            yes[i] = !guy[t];
            no[s] = true;
            // cout << i << " " << a[i].first << " " << a[i].second << endl;
            while (u!=v) {
                if (d[u] > d[v]) swap(u, v);
                v = fa[v];
                // cout << u << " " << v << endl;
                if (v != t) no[v] = true;
                if (v != s) yes[i] &= (!guy[v]);
            }
        }
        bool ok = false;
        for (int i=1;i<=n;i++) if (yes[i] && !no[i]) {
            // cout << a[i].first << " " << a[i].second << endl;
            guy[i] = true;
            guy[a[i].first] = false;
            a[i] = {-1, -1};
            ok = true;
            break;
        }
        if (!ok) {cout << "No\n"; return;}
    }
    cout << "Yes\n";
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
}

Compilation message (stderr)

jail.cpp: In function 'void dfs1(long long int)':
jail.cpp:24:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int j=1;j<ADJ[u].size();j++) if (sz[ADJ[u][j]] > sz[ADJ[u][0]]) swap(ADJ[u][0], ADJ[u][j]);
      |                  ~^~~~~~~~~~~~~~

• 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