oj.uz

Submission #781383

# Submission time Handle Problem Language Result Execution time Memory
781383 2023-07-13T05:05:22 Z IBory Jail (JOI22_jail) C++17
5 / 100
 251 ms 45404 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11604 KB Output is correct
2 Correct 5 ms 11604 KB Output is correct
3 Correct 5 ms 11604 KB Output is correct
4 Correct 51 ms 11860 KB Output is correct
5 Correct 76 ms 12256 KB Output is correct
6 Correct 10 ms 11604 KB Output is correct
7 Correct 8 ms 11604 KB Output is correct
8 Correct 9 ms 11600 KB Output is correct
9 Correct 60 ms 13772 KB Output is correct
10 Correct 75 ms 31356 KB Output is correct
11 Correct 49 ms 11748 KB Output is correct
12 Correct 103 ms 12524 KB Output is correct
13 Correct 141 ms 34644 KB Output is correct
14 Correct 108 ms 34544 KB Output is correct
15 Correct 108 ms 34584 KB Output is correct
16 Correct 154 ms 39256 KB Output is correct
17 Correct 160 ms 35328 KB Output is correct
18 Correct 251 ms 45404 KB Output is correct
19 Correct 153 ms 35244 KB Output is correct
20 Correct 140 ms 35272 KB Output is correct
21 Correct 110 ms 35388 KB Output is correct
22 Correct 108 ms 35268 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11604 KB Output is correct
2 Correct 6 ms 11604 KB Output is correct
3 Correct 9 ms 11664 KB Output is correct
4 Correct 8 ms 11600 KB Output is correct
5 Correct 8 ms 11600 KB Output is correct
6 Correct 8 ms 11604 KB Output is correct
7 Correct 8 ms 11604 KB Output is correct
8 Incorrect 8 ms 11632 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11604 KB Output is correct
2 Correct 6 ms 11604 KB Output is correct
3 Correct 9 ms 11664 KB Output is correct
4 Correct 8 ms 11600 KB Output is correct
5 Correct 8 ms 11600 KB Output is correct
6 Correct 8 ms 11604 KB Output is correct
7 Correct 8 ms 11604 KB Output is correct
8 Incorrect 8 ms 11632 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11604 KB Output is correct
2 Correct 6 ms 11604 KB Output is correct
3 Correct 9 ms 11664 KB Output is correct
4 Correct 8 ms 11600 KB Output is correct
5 Correct 8 ms 11600 KB Output is correct
6 Correct 8 ms 11604 KB Output is correct
7 Correct 8 ms 11604 KB Output is correct
8 Incorrect 8 ms 11632 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11604 KB Output is correct
2 Correct 6 ms 11604 KB Output is correct
3 Correct 9 ms 11664 KB Output is correct
4 Correct 8 ms 11600 KB Output is correct
5 Correct 8 ms 11600 KB Output is correct
6 Correct 8 ms 11604 KB Output is correct
7 Correct 8 ms 11604 KB Output is correct
8 Incorrect 8 ms 11632 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11604 KB Output is correct
2 Correct 5 ms 11604 KB Output is correct
3 Correct 5 ms 11604 KB Output is correct
4 Correct 6 ms 11604 KB Output is correct
5 Correct 51 ms 11740 KB Output is correct
6 Incorrect 7 ms 11604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11604 KB Output is correct
2 Correct 5 ms 11604 KB Output is correct
3 Correct 5 ms 11604 KB Output is correct
4 Correct 51 ms 11860 KB Output is correct
5 Correct 76 ms 12256 KB Output is correct
6 Correct 10 ms 11604 KB Output is correct
7 Correct 8 ms 11604 KB Output is correct
8 Correct 9 ms 11600 KB Output is correct
9 Correct 60 ms 13772 KB Output is correct
10 Correct 75 ms 31356 KB Output is correct
11 Correct 49 ms 11748 KB Output is correct
12 Correct 103 ms 12524 KB Output is correct
13 Correct 141 ms 34644 KB Output is correct
14 Correct 108 ms 34544 KB Output is correct
15 Correct 108 ms 34584 KB Output is correct
16 Correct 154 ms 39256 KB Output is correct
17 Correct 160 ms 35328 KB Output is correct
18 Correct 251 ms 45404 KB Output is correct
19 Correct 153 ms 35244 KB Output is correct
20 Correct 140 ms 35272 KB Output is correct
21 Correct 110 ms 35388 KB Output is correct
22 Correct 108 ms 35268 KB Output is correct
23 Correct 7 ms 11604 KB Output is correct
24 Correct 6 ms 11604 KB Output is correct
25 Correct 9 ms 11664 KB Output is correct
26 Correct 8 ms 11600 KB Output is correct
27 Correct 8 ms 11600 KB Output is correct
28 Correct 8 ms 11604 KB Output is correct
29 Correct 8 ms 11604 KB Output is correct
30 Incorrect 8 ms 11632 KB Output isn't correct
31 Halted 0 ms 0 KB -