oj.uz

Submission #132192

# Submission time Handle Problem Language Result Execution time Memory
132192 2019-07-18T12:40:46 Z mlyean00 Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 114392 KB 
#include "garden.h"
#include "gardenlib.h"

#include <bits/stdc++.h>

using namespace std;
using adj_list = vector<vector<int>>;

const int MAX = 1'000'000'000;

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    adj_list g(N);
    for (int i = 0; i < M; ++i) {
        g[R[i][0]].push_back(R[i][1]);
        g[R[i][1]].push_back(R[i][0]);
    }

    int k = __lg(MAX);
    vector<vector<pair<int, int>>> st0(N, vector<pair<int, int>>(k + 1));
    vector<vector<pair<int, int>>> st1(N, vector<pair<int, int>>(k + 1));

    for (int u = 0; u < N; ++u) {

        st0[u][0] = {g[u].size() == 1 ? g[u][0] : g[u][1], u};
        st1[u][0] = {g[u][0], u};
    }

    for (int i = 1; i <= k; ++i) {
        for (int u = 0; u < N; ++u) {
            int v, p;

            tie(v, p) = st0[u][i - 1];
            st0[u][i] = p == g[v][0] ? st0[v][i - 1] : st1[v][i - 1];

            tie(v, p) = st1[u][i - 1];
            st1[u][i] = p == g[v][0] ? st0[v][i - 1] : st1[v][i - 1];
        }
    }

    vector<pair<int, int>> query(Q);
    for (int q = 0; q < Q; ++q) {
        query[q] = {G[q], q};
    }
    sort(query.begin(), query.end());

    vector<int> ans(Q);

    int t = 0;
    vector<int> cnt0(N, 0);
    vector<int> cnt1(N, 1);

    set<int> alive;
    for (int i = 0; i < N; ++i) {
        alive.insert(i);
    }

    for (auto [q, id] : query) {
        map<int, int> delta0, delta1;

        int diff = q - t;
        t = q;
        for (int u : alive) {
            {
                int v = u, p = g[u][0];
                for (int j = diff; j; j -= j & -j) {
                    int s = __builtin_ctz(j);
                    tie(v, p) = g[v][0] == p ? st0[v][s] : st1[v][s];
                }

                if (p == g[v][0])
                    delta0[v] += cnt0[u];
                else
                    delta1[v] += cnt0[u];
                delta0[u] -= cnt0[u];
            }
            {
                int v = u, p = u;
                for (int j = diff; j; j -= j & -j) {
                    int s = __builtin_ctz(j);
                    tie(v, p) = g[v][0] == p ? st0[v][s] : st1[v][s];
                }

                if (p == g[v][0])
                    delta0[v] += cnt1[u];
                else
                    delta1[v] += cnt1[u];
                delta1[u] -= cnt1[u];
            }
        }

        for (auto [i, del] : delta0) {
            cnt0[i] += del;
            if (cnt0[i] == 0 && cnt1[i] == 0) alive.erase(i);
        }
        for (auto [i, del] : delta1) {
            cnt1[i] += del;
            if (cnt0[i] == 0 && cnt1[i] == 0) alive.erase(i);
        }

        ans[id] = cnt0[P] + cnt1[P];
    }

    for (int i : ans) {
        answer(i);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 888 KB Output is correct
2 Correct 4 ms 1016 KB Output is correct
3 Correct 4 ms 1016 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 5 ms 1144 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 4 ms 1016 KB Output is correct
9 Correct 6 ms 1144 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 888 KB Output is correct
2 Correct 4 ms 1016 KB Output is correct
3 Correct 4 ms 1016 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 5 ms 1144 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 4 ms 1016 KB Output is correct
9 Correct 6 ms 1144 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 94 ms 17428 KB Output is correct
12 Correct 202 ms 29104 KB Output is correct
13 Correct 716 ms 65020 KB Output is correct
14 Correct 789 ms 103108 KB Output is correct
15 Correct 766 ms 104552 KB Output is correct
16 Correct 588 ms 70700 KB Output is correct
17 Correct 388 ms 59764 KB Output is correct
18 Correct 163 ms 29096 KB Output is correct
19 Correct 805 ms 103080 KB Output is correct
20 Correct 736 ms 104264 KB Output is correct
21 Correct 534 ms 70692 KB Output is correct
22 Correct 412 ms 59476 KB Output is correct
23 Correct 1066 ms 114392 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 888 KB Output is correct
2 Correct 4 ms 1016 KB Output is correct
3 Correct 4 ms 1016 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 5 ms 1144 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 4 ms 1016 KB Output is correct
9 Correct 6 ms 1144 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 94 ms 17428 KB Output is correct
12 Correct 202 ms 29104 KB Output is correct
13 Correct 716 ms 65020 KB Output is correct
14 Correct 789 ms 103108 KB Output is correct
15 Correct 766 ms 104552 KB Output is correct
16 Correct 588 ms 70700 KB Output is correct
17 Correct 388 ms 59764 KB Output is correct
18 Correct 163 ms 29096 KB Output is correct
19 Correct 805 ms 103080 KB Output is correct
20 Correct 736 ms 104264 KB Output is correct
21 Correct 534 ms 70692 KB Output is correct
22 Correct 412 ms 59476 KB Output is correct
23 Correct 1066 ms 114392 KB Output is correct
24 Correct 16 ms 376 KB Output is correct
25 Execution timed out 5068 ms 17380 KB Time limit exceeded
26 Halted 0 ms 0 KB -