oj.uz

Submission #132167

# Submission time Handle Problem Language Result Execution time Memory
132167 2019-07-18T11:37:31 Z mlyean00 Tropical Garden (IOI11_garden) C++14
0 / 100
 3 ms 760 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;

adj_list g;

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    g = adj_list(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) {
        assert(!g[u].empty());

        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] = st1[v][i - 1];
        }
    }

    for (int q = 0; q < Q; ++q) {
        int ans = 0;
        for (int i = 0; i < N; ++i) {
            int u = i, p = i;
            for (int j = G[q]; j; j -= j & -j) {
                int s = __builtin_ctz(j);
                tie(u, p) = g[u][0] == p ? st0[u][s] : st1[u][s];
            }
            if (u == P) ++ans;
        }
        answer(ans);
    }
}

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -