제출 #1236377

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236377		vk3601h	열대 식물원 (Tropical Garden) (IOI11_garden)	C++20	100 / 100	1381 ms	23968 KiB

garden

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

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    vector<int> adj0(N, -1);
    vector<int> adj1(N, -1);

    for (int i = 0; i < M; ++i){
        int u = R[i][0];
        int v = R[i][1];

        if (adj0[u] == -1) adj0[u] = v;
        else if (adj1[u] == -1) adj1[u] = v;

        if (adj0[v] == -1) adj0[v] = u;
        else if (adj1[v] == -1) adj1[v] = u;
    }
    for (int i = 0; i < N; ++i) if (adj1[i] == -1) adj1[i] = adj0[i];

    auto next_state = [&](int state) -> int{
        int u = state / 2;
        int s = state % 2;

        int w = (s == 0) ? adj0[u] : adj1[u];

        if (adj0[w] == u) return 2 * w + 1;
        return 2 * w;
    };

    int total_state = 2 * N;

    vector<int> circle_size(total_state, 0);
    vector<int> first_visit(total_state, -1);
    vector<bool> in_circle(total_state, false);
    int time_stamp = 0;

    for (int start = 0; start < total_state; ++start){
        if (first_visit[start] != -1) continue;

        int slow = start, fast = start;
        do{
            slow = next_state(slow);
            fast = next_state(next_state(fast));
        } while (first_visit[slow] == -1 && first_visit[fast] == -1 && slow != fast);

        if (first_visit[slow] != -1 || first_visit[fast] != -1) continue;

        if (slow == fast){
            int circle_start = slow;
            vector<int> circle_nodes;

            int cur = circle_start;
            do{
                circle_nodes.push_back(cur);
                cur = next_state(cur);
            } while (cur != circle_start);

            int len = circle_nodes.size();
            for (int node : circle_nodes){
                circle_size[node] = len;
                in_circle[node] = true;
            }
        }

        int cur = start;
        while (first_visit[cur] == -1){
            first_visit[cur] = time_stamp++;
            cur = next_state(cur);
        }
    }

    int t0 = 2 * P;
    int t1 = 2 * P + 1;

    vector<int> dist0(total_state, -1);
    vector<int> dist1(total_state, -1);

    vector<vector<int>> rev_adj(total_state);
    for (int i = 0; i < total_state; ++i) rev_adj[next_state(i)].push_back(i);

    queue<int> q0;
    dist0[t0] = 0;
    q0.push(t0);
    while (!q0.empty()){
        int u = q0.front();
        q0.pop();
        for (int v : rev_adj[u]){
            if (dist0[v] == -1){
                dist0[v] = dist0[u] + 1;
                q0.push(v);
            }
        }
    }

    queue<int> q1;
    dist1[t1] = 0;
    q1.push(t1);
    while (!q1.empty()){
        int u = q1.front();
        q1.pop();
        for (int v : rev_adj[u]){
            if (dist1[v] == -1){
                dist1[v] = dist1[u] + 1;
                q1.push(v);
            }
        }
    }

    int c0 = circle_size[t0];
    int c1 = circle_size[t1];

    for (int idx = 0; idx < Q; ++idx){
        long long K = G[idx];
        int ans = 0;

        for (int u = 0; u < N; ++u){
            int s0 = u * 2;

            if (dist0[s0] != -1){
                if (c0 == 0) {if (dist0[s0] == K) ans++;}
                else {if (K >= dist0[s0] && (K - dist0[s0]) % c0 == 0) ans++;}
            }

            if (dist1[s0] != -1){
                if (c1 == 0) {if (dist1[s0] == K) ans++;}
                else {if (K >= dist1[s0] && (K - dist1[s0]) % c1 == 0) ans++;}
            }
        }

        answer(ans);
    }
}

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