Submission #781383

#	Time	Username	Problem	Language	Result	Execution time	Memory
781383		IBory	Jail (JOI22_jail)	C++17	5 / 100	251 ms	45404 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], EG[SZ];
pii E[SZ];
int D[SZ], P[SZ], Z[SZ], R[SZ], in[SZ], out[SZ], dn;
int ES[SZ], C[SZ], ind[SZ];

void MakeG(int cur, int prev) {
    P[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;
}

void DFS3(int cur, int pe) {
    if (pe != -1 && ES[cur] >= 0) {
        EG[ES[cur]].push_back(pe);
        ind[pe]++;
        for (int next : G[cur]) DFS3(next, ES[cur]);
    }
    else for (int next : G[cur]) DFS3(next, pe);
}

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

struct Seg {
    int T[SZ << 1];
    void Clear() {
        memset(T, -1, sizeof(T));
    }
    void Update(int i, int v) {
        T[i += SZ - 1] = v;
        while (i >>= 1) T[i] = max(T[i * 2], T[i * 2 + 1]);
    }
    int Query(int L, int R, int sL = 1, int sR = SZ, int n = 1) {
        if (L > R || R < sL || sR < L) return -1;
        if (L <= sL && sR <= R) return T[n];
        int mid = (sL + sR) >> 1;
        return max(Query(L, R, sL, mid, n * 2), Query(L, R, mid + 1, sR, n * 2 + 1));
    }
    int PathQuery(int a, int b) {
        //printf("PQ %d %d\n", a, b);
        int ret = -1;
        while (R[a] != R[b]) {
            if (D[R[a]] > D[R[b]]) swap(a, b);
            ret = max(ret, Query(in[R[b]], in[b]));
            b = P[R[b]];
        }
        if (D[a] > D[b]) swap(a, b);
        return max(ret, Query(in[a], in[b]));
    }
} T;

int main() {
    int test;
    cin >> test;
    while (test--) {
        int N, Q, no = 0;
        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 >> Q;
        for (int i = 0; i < Q; ++i) cin >> E[i].first >> E[i].second;

        dn = 0;
        MakeG(1, 1);
        DFS(1);
        DFS2(1, 1);

        memset(ind, 0, sizeof(ind));
        fill(ES, ES + N, -1);
        for (int i = 0; i < Q; ++i) ES[E[i].second] = i;
        DFS3(1, -1);

        T.Clear();
        for (int i = 0; i < Q; ++i) T.Update(in[E[i].first], i);
        memset(C, 0, sizeof(C));
        set<int> cand;
        for (int i = 0; i < Q; ++i) {
            if (!ind[i]) cand.insert(i);
        }

        while (!cand.empty()) {
            int init = *cand.begin();
            //printf("Start at: %d\n", init);
            vector<int> ST;
            set<int> V;
            ST.push_back(init); V.insert(init);
            while (!ST.empty()) {
                int cur = ST.back();
                T.Update(in[E[cur].first], -1);
                int t = T.PathQuery(E[cur].first, E[cur].second);
                T.Update(in[E[cur].first], cur);
                //cout << cur << ' ' << t << '\n';
                //cout.flush();
                if (t == 1e9 || V.find(t) != V.end() || (t != -1 && cand.find(t) == cand.end())) {
                    no = 1;
                    goto END;
                }
                else if (t != -1) {
                    ST.push_back(t); V.insert(t);
                    continue;
                }
                if (!EG[cur].empty() && !--ind[EG[cur][0]]) {
                    cand.insert(EG[cur][0]);
                }
                T.Update(in[E[cur].first], -1);
                T.Update(in[E[cur].second], 1e9);
                cand.erase(cur);
                ST.pop_back();
            }

        }

END:
        cout << (no ? "No" : "Yes") << '\n';
        for (int i = 1; i <= N; ++i) {
            G[i].clear();
            TG[i].clear();
            EG[i].clear();
        }
    }
    return 0;
}

Compilation message (stderr)

jail.cpp: In function 'int DFS(int)':
jail.cpp:23:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int i = 0; i < G[cur].size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~
jail.cpp: In function 'void DFS2(int, int)':
jail.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i = 0; i < G[cur].size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~

• Subtask 1: 5 / 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