Submission #1000337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000337		onbert	Jail (JOI22_jail)	C++17	0 / 100	8 ms	15560 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;
}

int S[maxn], T[maxn];
bool vis[maxn], die = false;
int rt[maxn];

int root(int u) {
    if (rt[u] == u) return u;
    else return rt[u] = root(rt[u]);
}

void dfs3(int u) {
    vis[u] = true;
    int x = u, y = S[u];
    vector<int> path = {x, y};
    while (x!=y) {
        if (d[x] > d[y]) swap(x, y);
        y = fa[y];
        path.push_back(y);
    }
    for (int v:path) if (T[v]!=-1 && T[v] != u) {
        if (!vis[T[v]]) dfs3(T[v]);
    }
    for (int v:path) if (T[v]!=-1 && T[v] != u) {
        rt[root(T[v])] = root(u);
        // cout << "merge " << T[v] << " " << u << endl;
    }
    for (int v:path) if (S[v] != -1 && v!=u) {
        die |= (root(v) == root(u));
        // if (root(v) == root(u)) cout << u << " " << v << " " << root(u) << endl;
    }
}

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++) S[i] = -1, T[i] = -1, vis[i] = false, rt[i] = i;
    cin >> m;
    for (int i=1;i<=m;i++) {
        int s, t;
        cin >> s >> t;
        s = newid[s], t = newid[t];
        T[s] = t;
        S[t] = s;
    }
    die = false;
    for (int i=1;i<=n;i++) if (S[i]!=-1 && !vis[i]) {
        dfs3(i);
        // cout << i << endl;
    }
    if (die) cout << "No\n";
    else 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]);
      |                  ~^~~~~~~~~~~~~~
jail.cpp: In function 'void solve()':
jail.cpp:80:10: warning: variable 'guy' set but not used [-Wunused-but-set-variable]
   80 |     bool guy[n+1];
      |          ^~~

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