제출 #1274500

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274500		gkishor03	Tropical Garden (IOI11_garden)	C++20	49 / 100	5091 ms	4788 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

struct State {
    int node, prev;
};

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    // Build adjacency with beauty order
    vector<vector<int>> adj(N);
    for (int i = 0; i < M; i++) {
        int u = R[i][0], v = R[i][1];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // For each node, we already know adjacency list is in order of beauty,
    // since trails were given in decreasing beauty order.
    // So the first neighbor in adj[u] is the most beautiful, second is 2nd most.
    // (If more than 2 neighbors, we only care about the first 2.)
    vector<int> best(N, -1), second(N, -1);
    for (int u = 0; u < N; u++) {
        if (!adj[u].empty()) best[u] = adj[u][0];
        if (adj[u].size() >= 2) second[u] = adj[u][1];
    }

    // Answer queries one by one (Q = 1 in Subtask 1 anyway)
    for (int qi = 0; qi < Q; qi++) {
        int K = G[qi];
        long long result = 0;

        // BFS/DP: state = (current node, previous node), step number
        map<pair<int,int>, long long> cur, nxt;
        // initial: can start from any node, with prev = -1
        for (int u = 0; u < N; u++) {
            cur[{u, -1}] = 1;
        }

        for (int step = 0; step < K; step++) {
            nxt.clear();
            for (auto &entry : cur) {
                int u = entry.first.first;
                int prev = entry.first.second;
                long long ways = entry.second;

                // Choose next neighbor according to rules
                int go = -1;
                if (best[u] != -1 && best[u] != prev) {
                    go = best[u];
                } else if (second[u] != -1 && second[u] != prev) {
                    go = second[u];
                } else {
                    // must go back to prev
                    go = prev;
                }

                nxt[{go, u}] += ways;
            }
            cur.swap(nxt);
        }

        // Count how many end at P
        for (auto &entry : cur) {
            int u = entry.first.first;
            long long ways = entry.second;
            if (u == P) result += ways;
        }

        answer(result);
    }
}

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