제출 #132181

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
132181		mlyean00	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	69 / 100	5029 ms	92140 KiB

garden

#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) {
        if (g[u].empty()) continue;

        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) {
            if (g[u].empty()) continue;
            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];
        }
    }

    for (int q = 0; q < Q; ++q) {
        int ans = 0;
        for (int i = 0; i < N; ++i) {
            if (g[i].empty()) continue;
            int u = i, p = -1;
            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: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 0 / 31