제출 #132192

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
132192		mlyean00	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	69 / 100	5068 ms	114392 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) {

        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 / 49
• Subtask 2: 20 / 20
• Subtask 3: 0 / 31