제출 #1218062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1218062		asturnox	Tropical Garden (IOI11_garden)	C++20	0 / 100	1 ms	580 KiB

garden

#include "garden.h"
#include "gardenlib.h"

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cstdint>
#include <algorithm>
#include <cmath>

using namespace std;
using StateKey = uint64_t;

inline StateKey pack_state(int walk, int prev) {
    return (uint64_t(walk) << 32) | uint32_t(prev);
}

void answer(int X);

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    // 1) Build adjacency lists (up to 2 edges per node)
    vector<vector<int>> node_edges(N);
    node_edges.reserve(N);
    for (int idx = 0; idx < M; ++idx) {
        int u = R[idx][0];
        int v = R[idx][1];
        if (node_edges[u].size() < 2) node_edges[u].push_back(v);
        if (node_edges[v].size() < 2) node_edges[v].push_back(u);
    }

    // 2) Enumerate all possible states (walk, prev)
    vector<pair<int,int>> states;
    states.reserve(2 * N);
    for (int u = 0; u < N; ++u) {
        if (node_edges[u].empty()) {
            // isolated or dead end: self-loop state
            states.emplace_back(u, u);
        } else {
            for (int v : node_edges[u]) {
                states.emplace_back(u, v);
            }
        }
    }
    int S = states.size();

    // 3) Map each state to a compact ID
    unordered_map<StateKey, int> state_id;
    state_id.reserve(S);
    for (int i = 0; i < S; ++i) {
        state_id[pack_state(states[i].first, states[i].second)] = i;
    }

    // 4) Precompute successor and node_of_state arrays
    vector<int> succ(S), node_of_state(S);
    for (int i = 0; i < S; ++i) {
        int walk = states[i].first;
        int prev = states[i].second;
        // do_walk:
        int next = walk;
        if (!node_edges[walk].empty()) {
            next = node_edges[walk][0];
            if (node_edges[walk].size() == 2 && next == prev)
                next = node_edges[walk][1];
        }
        StateKey key = pack_state(next, walk);
        succ[i] = state_id[key];
        node_of_state[i] = walk;
    }

    // 5) Precompute binary-lifting table for fast jumps
    int maxG = 0;
    for (int i = 0; i < Q; ++i) maxG = max(maxG, G[i]);
    int LOG = (maxG > 0 ? floor(log2(maxG)) + 1 : 1);
    vector<vector<int>> lift(LOG, vector<int>(S));
    // lift[0] = direct successor
    lift[0] = succ;
    for (int k = 1; k < LOG; ++k) {
        for (int i = 0; i < S; ++i) {
            lift[k][i] = lift[k-1][ lift[k-1][i] ];
        }
    }

    // 6) Precompute initial state IDs for each starting node
    vector<int> init_state(N);
    for (int u = 0; u < N; ++u) {
        if (node_edges[u].empty()) {
            init_state[u] = state_id[pack_state(u, u)];
        } else {
            int first = node_edges[u][0];
            init_state[u] = state_id[pack_state(first, u)];
        }
    }

    // 7) Answer each query in O(N * LOG)
    for (int qi = 0; qi < Q; ++qi) {
        int g = G[qi];
        int cnt = 0;
        for (int u = 0; u < N; ++u) {
            int s = init_state[u];
            int steps = g;
            for (int k = 0; k < LOG; ++k) {
                if (steps & (1 << k)) {
                    s = lift[k][s];
                }
            }
            if (node_of_state[s] == P) {
                ++cnt;
            }
        }
        answer(cnt);
    }
}

• Subtask 1: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31