제출 #1235846

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1235846		vk3601h	Tropical Garden (IOI11_garden)	C++20	100 / 100	1355 ms	25560 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <vector>
#include <queue>
#include <algorithm>
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;
        else return 2 * w;
    };
    
    int total_states = 2 * N;
    vector<int> deg_in(total_states, 0);
    vector<vector<int>> rev_adj(total_states);
    
    for (int i = 0; i < total_states; i++) {
        int j = next_state(i);
        deg_in[j]++;
        rev_adj[j].push_back(i);
    }
    
    vector<int> deg = deg_in;
    queue<int> q_deg;
    for (int i = 0; i < total_states; i++) {
        if (deg[i] == 0) q_deg.push(i);
    }
    while (!q_deg.empty()) {
        int u = q_deg.front(); q_deg.pop();
        int v = next_state(u);
        if (--deg[v] == 0) q_deg.push(v);
    }
    
    vector<int> cycle_size(total_states, 0);
    vector<bool> global_vis(total_states, false);
    for (int i = 0; i < total_states; i++) {
        if (deg[i] <= 0) continue;
        if (global_vis[i]) continue;
        vector<int> stack;
        vector<int> local_vis(total_states, -1);
        int cur = i;
        while (local_vis[cur] == -1) {
            local_vis[cur] = stack.size();
            stack.push_back(cur);
            global_vis[cur] = true;
            cur = next_state(cur);
        }
        int idx = local_vis[cur];
        int len = stack.size() - idx;
        for (int j = idx; j < stack.size(); j++) {
            cycle_size[stack[j]] = len;
        }
    }
    
    int t0 = 2 * P;
    int t1 = 2 * P + 1;
    vector<int> dist0(total_states, -1);
    vector<int> dist1(total_states, -1);
    
    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);
            }
        }
    }
    
    for (int idx = 0; idx < Q; idx++) {
        long long K = G[idx];
        int ans = 0;
        for (int u = 0; u < N; u++) {
            int s0 = 2 * u;
            if (dist0[s0] != -1) {
                if (cycle_size[t0] == 0) {
                    if (dist0[s0] == K) ans++;
                } else {
                    if (K >= dist0[s0] && (K - dist0[s0]) % cycle_size[t0] == 0) ans++;
                }
            }
            if (dist1[s0] != -1) {
                if (cycle_size[t1] == 0) {
                    if (dist1[s0] == K) ans++;
                } else {
                    if (K >= dist1[s0] && (K - dist1[s0]) % cycle_size[t1] == 0) ans++;
                }
            }
        }
        answer(ans);
    }
}

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