Submission #1263501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263501		patgra	Jail (JOI22_jail)	C++20	100 / 100	3181 ms	691776 KiB

jail

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

int n, m, mxLg;
vector<vector<int>> g, jp, g2, g2r;
vector<int> dep, vis, scc, post;
vector<pair<int, int>> st;
int tpost;

void dfs(int v, int p) {
    jp[v][0] = p;
    dep[v] = dep[p] + 1;
    repIn(u, g[v]) if(u != p) dfs(u, v);
}

int lca(int x, int y) {
    if(dep[x] > dep[y]) swap(x, y);
    repD(i, mxLg - 1, -1) if(dep[jp[y][i]] >= dep[x]) y = jp[y][i];
    if(x == y) return x;
    repD(i, mxLg - 1, -1) if(jp[x][i] != jp[y][i]) x = jp[x][i], y = jp[y][i];
    return jp[x][0];
}

void dfs2(int v) {
    vis[v] = true;
    repIn(u, g2[v]) if(!vis[u]) dfs2(u);
    post[tpost++] = v;
}

void dfs3(int v, int c) {
    scc[v] = c;
    repIn(u, g2r[v]) if(!scc[u]) dfs3(u, c);
}

void solve() {
    cin >> n;
    g.resize(n + 1);
    dep.resize(n + 1);
    rep(i, 1, n) {
        int a, b;
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }
    cin >> m;
    st.resize(m);
    rep(i, 0, m) cin >> st[i].first >> st[i].second;

    mxLg = 32 - __builtin_clz(n);
    jp.resize(n + 1, vector<int>(mxLg));
    dfs(1, 1);
    rep(k, 1, mxLg) rep(i, 1, n + 1) jp[i][k] = jp[jp[i][k - 1]][k - 1];

    g2.resize(n * 2 * mxLg + m + 1);
    g2r.resize(n * 2 * mxLg + m + 1);
    rep(k, 0, mxLg - 1) rep(i, 1, n + 1) {
        g2[n * 2 * k + i].pb(n * 2 * (k + 1) + i);
        g2[n * 2 * k + jp[i][k]].pb(n * 2 * (k + 1) + i);
        //g2[n * 2 * k + n + i].pb(n * 2 * (k + 1) + n + i);
        //g2[n * 2 * k + n + jp[i][k]].pb(n * 2 * (k + 1) + n + i);
        //g2[n * 2 * (k + 1) + i].pb(n * 2 * k + i);
        //g2[n * 2 * (k + 1) + i].pb(n * 2 * k + jp[i][k]);
        g2[n * 2 * (k + 1) + n + i].pb(n * 2 * k + n + i);
        g2[n * 2 * (k + 1) + n + i].pb(n * 2 * k + n + jp[i][k]);
    }
    rep(i, 0, m) {
        auto [s, t] = st[i];
        auto mlca = lca(s, t);
        g2[n * 2 * mxLg + 1 + i].pb(s);
        g2[n + t].pb(n * 2 * mxLg + 1 + i);
        repD(j, mxLg - 1, -1) if(dep[jp[s][j]] >= dep[mlca]) {
            g2[n * 2 * j + s].pb(n * 2 * mxLg + i + 1);
            g2[n * 2 * mxLg + i + 1].pb(n * 2 * j + n + s);
            s = jp[s][j];
        }
        g2[s].pb(n * 2 * mxLg + i + 1);
        g2[n * 2 * mxLg + i + 1].pb(n + s);
        repD(j, mxLg - 1, -1) if(dep[jp[t][j]] >= dep[mlca]) {
            g2[n * 2 * j + t].pb(n * 2 * mxLg + i + 1);
            g2[n * 2 * mxLg + i + 1].pb(n * 2 * j + n + t);
            t = jp[t][j];
        }
    }
    rep(i, 0, (int)g2.size()) rep(j, 0, (int)g2[i].size()) {
        DC << i << ' ' << g2[i][j] << eol;
        g2r[g2[i][j]].pb(i);
    }

    vis.resize(g2.size());
    post.resize(g2.size());
    rep(i, 0, (int)g2.size()) if(!vis[i]) dfs2(i);
    ranges::reverse(post);
    scc.resize(g2.size());
    repIn(i, post) if(!scc[i]) dfs3(i, i);
    DC << eol;
    rep(i, 1, (int)g2.size()) DC << i << ' ' << scc[i] << eol;
    bool gg = true;
    rep(i, 0, m) {
        gg = gg && vis[scc[2 * n * mxLg + 1 + i]] >= 0;
        vis[scc[2 * n * mxLg + 1 + i]] = -1;
    }
    cout << (gg ? "Yes" : "No") << '\n';

    g.clear(); jp.clear(); g2.clear(); g2r.clear();
    dep.clear(); vis.clear(); scc.clear(); post.clear();
    st.clear();
    tpost = 0;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int t;
    cin >> t;
    rep(i, 0, t) solve();
}

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