Submission #781669

#	Time	Username	Problem	Language	Result	Execution time	Memory
781669		IBory	Jail (JOI22_jail)	C++17	100 / 100	951 ms	100292 KiB

jail

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int SZ = 1 << 17;
vector<int> TG[SZ], G[SZ], G2[SZ << 3];
pii E[SZ];
int D[SZ], P[17][SZ], Z[SZ], R[SZ], in[SZ], out[SZ], id[SZ << 3], dn;

void MakeG(int cur, int prev) {
    P[0][cur] = prev;
    D[cur] = D[prev] + 1;
    for (int next : TG[cur]) {
        if (next == prev) continue;
        G[cur].push_back(next);
        MakeG(next, cur);
    }
}

int DFS(int cur) {
    int& ret = Z[cur] = 1;
    for (int i = 0; i < G[cur].size(); ++i) {
        int next = G[cur][i];
        ret += DFS(next);
        if (Z[next] > Z[G[cur][0]]) swap(G[cur][0], G[cur][i]);
    }
    return ret;
}

void DFS2(int cur, int top) {
    in[cur] = ++dn;
    R[cur] = top;
    for (int i = 0; i < G[cur].size(); ++i) {
        int next = G[cur][i];
        DFS2(next, (i == 0 ? top : next));
    }
    out[cur] = dn;
}

int LCA(int a, int b) {
    while (R[a] != R[b]) {
        if (D[R[a]] > D[R[b]]) swap(a, b);
        b = P[0][R[b]];
    }
    return (D[a] > D[b] ? b : a);
}

void Segment(int L, int R, vector<int>& node, int sL, int sR, int n = 1) {
    if (R < sL || sR < L) return;
    if (L <= sL && sR <= R) {
        node.push_back(n);
        return;
    }
    int mid = (sL + sR) >> 1;
    Segment(L, R, node, sL, mid, n * 2);
    Segment(L, R, node, mid + 1, sR, n * 2 + 1);
}

vector<int> Decompose(int s, int e, int CZ) {
    vector<pii> seg;
    vector<int> ret;
    int c = LCA(s, e);
    if (c == s) {
        int t = e, d = D[e] - D[s] - 1;
        for (int i = 16; i >= 0; --i) if (d & (1 << i)) t = P[i][t];
        s = t;
    }
    else s = P[0][s];

    while (R[s] != R[e]) {
        if (D[R[s]] > D[R[e]]) swap(s, e);
        seg.emplace_back(in[R[e]], in[e]);
        e = P[0][R[e]];
    }
    if (D[s] > D[e]) swap(s, e);
    seg.emplace_back(in[s], in[e]);

    for (auto [a, b] : seg) Segment(a, b, ret, 1, CZ);
    return ret;
}

int main() {
    int test;
    cin >> test;
    while (test--) {
        int N, M, no = 0, CZ = 1;
        cin >> N;
        for (int i = 1; i < N; ++i) {
            int a, b;
            cin >> a >> b;
            TG[a].push_back(b);
            TG[b].push_back(a);
        }
        cin >> M;
        for (int i = 1; i <= M; ++i) cin >> E[i].first >> E[i].second;
        while (CZ < N) CZ <<= 1;

        dn = 0;
        MakeG(1, 1);
        DFS(1);
        DFS2(1, 1);
        for (int i = 1; i < 17; ++i) for (int n = 1; n <= N; ++n) P[i][n] = P[i - 1][P[i - 1][n]];

        memset(id, 0, sizeof(id));
        for (int i = 1; i <= M; ++i) {
            auto [s, e] = E[i];
            vector<int> from = Decompose(s, e, CZ);
            vector<int> to = Decompose(e, s, CZ);
            for (int& n : to) n += CZ * 2;
            int cur = CZ * 4 + i;
            for (int n : from) G2[n].push_back(cur), id[cur]++;
            for (int n : to) G2[cur].push_back(n), id[n]++;
            G2[cur].push_back(in[s] + CZ - 1), id[in[s] + CZ - 1]++;
            G2[in[e] + CZ * 3 - 1].push_back(cur), id[cur]++;
        }
        
        for (int i = 1; i < CZ; ++i) {
            G2[i * 2].push_back(i), id[i]++;
            G2[i * 2 + 1].push_back(i), id[i]++;
            int t = CZ * 2;
            G2[t + i].push_back(t + i * 2), id[t + i * 2]++;
            G2[t + i].push_back(t + i * 2 + 1), id[t + i * 2 + 1]++;
        }

        queue<int> Q;
        int cnt = CZ * 4 + M;
        for (int i = 1; i <= CZ * 4 + M; ++i) {
            if (!id[i]) Q.push(i);
        }

        while (!Q.empty()) {
            int cur = Q.front(); Q.pop();
            cnt--;
            for (int next : G2[cur]) {
                if (!--id[next]) Q.push(next);
            }
        }

        cout << (cnt ? "No" : "Yes") << '\n';
        for (int i = 1; i <= N; ++i) {
            G[i].clear();
            TG[i].clear();
        }
        for (int i = 0; i < (CZ * 8); ++i) G2[i].clear();
    }
    return 0;
}

Compilation message (stderr)

jail.cpp: In function 'int DFS(int)':
jail.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0; i < G[cur].size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~
jail.cpp: In function 'void DFS2(int, int)':
jail.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0; i < G[cur].size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~
jail.cpp: In function 'int main()':
jail.cpp:86:19: warning: unused variable 'no' [-Wunused-variable]
   86 |         int N, M, no = 0, CZ = 1;
      |                   ^~

• 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