제출 #944692

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
944692		Pring	Jail (JOI22_jail)	C++17	100 / 100	1052 ms	258452 KiB

jail

#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

// #define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 120005, LG = 17;
int n, m, s[MXN], t[MXN];

enum ID_PREF {
    NUM_ID = 0,
    S_TREE_ID = 1,
    T_TREE_ID = LG + 1
};

int f(int x, int y) {
    return x * MXN + y;
}

namespace GRAPH {
    vector<pii> edge;
    int lst[MXN * (2 * LG + 1)];
    int dfn[MXN * (2 * LG + 1)], low[MXN * (2 * LG + 1)], scc[MXN * (2 * LG + 1)], C, nc;
    vector<int> st;

    void init() {
        FOR(i, 0, 2 * LG + 1) {
            FOR(j, 1, n + 1) {
                lst[f(i, j)] = -1;
            }
        }
    }

    void add_edge(int x, int y, bool rev = false) {
        if (rev) swap(x, y);
        // debug(x, y);
        edge.push_back(mp(y, lst[x]));
        lst[x] = edge.size() - 1;
    }

    void DFS(int id) {
        C++;
        dfn[id] = C;
        low[id] = C;
        st.push_back(id);
        if (lst[id] != -1) {
            for (pii now = edge[lst[id]]; true; now = edge[now.sc]) {
                int i = now.fs;
                if (scc[i]) {
                    if (now.sc == -1) break;
                    continue;
                }
                if (dfn[i]) {
                    low[id] = min(low[id], dfn[i]);
                } else {
                    DFS(i);
                    low[id] = min(low[id], low[i]);
                }
                if (now.sc == -1) break;
            }
        }
        if (low[id] == dfn[id]) {
            int x;
            nc++;
            do {
                x = st.back();
                st.pop_back();
                scc[x] = nc;
            } while (x != id);
        }
    }

    void SCC() {
        FOR(pi, 0, 2 * LG + 1) FOR(i, 1, n + 1) {
            int id = f(pi, i);
            if (dfn[id]) continue;
            DFS(id);
        }
    }

    bool check() {
        // debug();
        // FOR(i, 1, m + 1) cout << scc[i] << ' ';
        // cout << endl;
        // debug();
        sort(scc + 1, scc + m + 1);
        FOR(i, 1, m) if (scc[i] == scc[i + 1]) return false;
        return true;
    }

    void RESET() {
        edge.clear();
        C = 0;
        nc = 0;
        FOR(i, 0, 2 * LG + 1) {
            FOR(j, 1, n + 1) {
                int id = f(i, j);
                dfn[id] = 0;
                low[id] = 0;
                scc[id] = 0;
            }
        }
    }
}

namespace TREE {
    vector<int> edge[MXN];
    int p[LG][MXN], d[MXN];

    void push_edge(int x, int y) {
        edge[x].push_back(y);
        edge[y].push_back(x);
    }

    void DFS(int id, int par, int dep) {
        p[0][id] = par;
        d[id] = dep;
        for (auto &i : edge[id]) {
            if (i == par) continue;
            DFS(i, id, dep + 1);
        }
    }

    void build_p() {
        DFS(1, 1, 0);
        FOR(i, 0, LG - 1) {
            FOR(j, 1, n + 1) {
                p[i + 1][j] = p[i][p[i][j]];
            }
        }
    }

    int leap_bin(int x, int w, vector<pii> &vnd) {
        vnd.push_back(mp(w, x));
        return p[w][x];
    }
    
    int leap(int x, int k, vector<pii> &vnd) {
        // debug(x, k);
        for (int w = LG - 1; w >= 0; w--) {
            if (k & (1 << w)) {
                x = leap_bin(x, w, vnd);
            }
        }
        // debug(x);
        return x;
    }

    vector<pii> LCA(int x, int y) {
        vector<pii> vnd;
        if (d[x] < d[y]) swap(x, y);
        x = leap(x, d[x] - d[y], vnd);
        // debug(x, y, d[x], d[y]);
        if (x == y) {
            vnd.push_back(mp(0LL, x));
            return vnd;
        }
        for (int w = LG - 1; w >= 0; w--) {
            if (p[w][x] == p[w][y]) continue;
            x = leap_bin(x, w, vnd);
            y = leap_bin(y, w, vnd);
        }
        vnd.push_back(mp(1LL, x));
        vnd.push_back(mp(1LL, y));
        return vnd;
    }

    void RESET() {
        FOR(i, 1, n + 1) {
            edge[i].clear();
            d[i] = 0;
        }
        FOR(i, 0, LG) fill(p[i] + 1, p[i] + n + 1, 0);
    }
}

struct TREE_AGENT {
    int sr;
    bool rev;

    void init(int _sr, bool _rev) {
        sr = _sr;
        rev = _rev;
    }

    void connect() {
        FOR(w, 0, LG - 1) {
            FOR(i, 1, n + 1) {
                GRAPH::add_edge(f(sr + w + 1, i), f(sr + w, i), rev);
                GRAPH::add_edge(f(sr + w + 1, i), f(sr + w, TREE::p[w][i]), rev);
            }
        }
    }

    void add_edge(int x, vector<pii> vnd) {
        for (auto &i : vnd) {
            GRAPH::add_edge(x, f(i.fs + sr, i.sc), rev);
        }
    }
} sa, ta;

bool miku() {
    int x, y;
    cin >> n;
    GRAPH::init();
    FOR(i, 1, n) {
        cin >> x >> y;
        TREE::push_edge(x, y);
    }
    TREE::build_p();
    sa.init(ID_PREF::S_TREE_ID, 1);
    ta.init(ID_PREF::T_TREE_ID, 0);
    sa.connect();
    ta.connect();
    cin >> m;
    FOR(i, 1, m + 1) {
        cin >> s[i] >> t[i];
        GRAPH::add_edge(f(ID_PREF::NUM_ID, i), f(ID_PREF::S_TREE_ID, s[i]));
        GRAPH::add_edge(f(ID_PREF::T_TREE_ID, t[i]), f(ID_PREF::NUM_ID, i));
        vector<pii> vnd = TREE::LCA(s[i], t[i]);
        // for (auto &i : vnd) {
        //     cout << i.fs << ' ' << i.sc << endl;
        // }
        // cout << endl;
        sa.add_edge(i, vnd);
        ta.add_edge(i, vnd);
    }
    GRAPH::SCC();
    return GRAPH::check();
}

void RESET() {
    GRAPH::RESET();
    TREE::RESET();
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    int t;
    cin >> t;
    while (t--) {
        cout << (miku() ? "Yes" : "No") << '\n';
        RESET();
    }
    return 0;
}

• 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