Submission #1162673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162673		spongb	열대 식물원 (Tropical Garden) (IOI11_garden)	C++20	0 / 100	5096 ms	320 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[]) {
    // Step 1: Compute the most beautiful and second most beautiful edges for each node
    vector<int> most_beautiful(N, -1);
    vector<int> second_most_beautiful(N, -1);
    
    // Process edges to find most and second most beautiful connections
    for (int i = 0; i < M; i++) {
        int a = R[i][0], b = R[i][1];
        
        // For node a
        if (most_beautiful[a] == -1) {
            most_beautiful[a] = b;
        } else if (second_most_beautiful[a] == -1) {
            second_most_beautiful[a] = b;
        }
        
        // For node b
        if (most_beautiful[b] == -1) {
            most_beautiful[b] = a;
        } else if (second_most_beautiful[b] == -1) {
            second_most_beautiful[b] = a;
        }
    }
    
    // For nodes with only one edge, use the same edge as both most and second most beautiful
    for (int i = 0; i < N; i++) {
        if (second_most_beautiful[i] == -1) {
            second_most_beautiful[i] = most_beautiful[i];
        }
    }
    
    // Step 2: Build the successor graph (functional graph where each node has exactly one outgoing edge)
    // We have 2*N nodes: nodes 0 to N-1 represent original nodes, nodes N to 2N-1 represent alternative states
    vector<int> next(2 * N, -1);
    
    for (int i = 0; i < N; i++) {
        int f = most_beautiful[i];
        int s = second_most_beautiful[i];
        
        // Determine successors based on how we arrive at each node
        next[i] = (most_beautiful[f] == i) ? f + N : f;
        next[i + N] = (most_beautiful[s] == i) ? s + N : s;
    }
    
    // Step 3: Find cycle lengths using Floyd's tortoise and hare algorithm
    // Find cycle for node P
    int cycle_len1 = INT_MAX;
    int tortoise = P, hare = next[P];
    
    // Detect cycle
    while (tortoise != hare && hare != -1) {
        tortoise = next[tortoise];
        hare = next[hare];
        if (hare != -1) hare = next[hare];
    }
    
    if (hare != -1) { // Cycle exists
        // Find cycle length
        tortoise = P;
        int steps = 0;
        
        // Find entry point to cycle
        while (tortoise != hare) {
            tortoise = next[tortoise];
            hare = next[hare];
            steps++;
        }
        
        // Measure cycle length
        int cycle_start = tortoise;
        cycle_len1 = 1;
        tortoise = next[tortoise];
        
        while (tortoise != cycle_start) {
            cycle_len1++;
            tortoise = next[tortoise];
        }
    }
    
    // Find cycle for node P+N (alternative state)
    int cycle_len2 = INT_MAX;
    tortoise = P + N;
    hare = next[P + N];
    
    // Detect cycle
    while (tortoise != hare && hare != -1) {
        tortoise = next[tortoise];
        hare = next[hare];
        if (hare != -1) hare = next[hare];
    }
    
    if (hare != -1) { // Cycle exists
        // Find cycle length
        tortoise = P + N;
        int steps = 0;
        
        // Find entry point to cycle
        while (tortoise != hare) {
            tortoise = next[tortoise];
            hare = next[hare];
            steps++;
        }
        
        // Measure cycle length
        int cycle_start = tortoise;
        cycle_len2 = 1;
        tortoise = next[tortoise];
        
        while (tortoise != cycle_start) {
            cycle_len2++;
            tortoise = next[tortoise];
        }
    }
    
    // Step 4: Compute distances using BFS (more memory-efficient than recursive DFS)
    vector<int> dist1(2 * N, -1);
    vector<int> dist2(2 * N, -1);
    
    // Build reverse graph for BFS
    vector<vector<int>> rev_graph(2 * N);
    for (int i = 0; i < 2 * N; i++) {
        if (next[i] != -1) {
            rev_graph[next[i]].push_back(i);
        }
    }
    
    // BFS from node P
    queue<int> q1;
    q1.push(P);
    dist1[P] = 0;
    
    while (!q1.empty()) {
        int v = q1.front();
        q1.pop();
        
        for (int u : rev_graph[v]) {
            if (dist1[u] == -1) {
                dist1[u] = dist1[v] + 1;
                q1.push(u);
            }
        }
    }
    
    // BFS from node P+N
    queue<int> q2;
    q2.push(P + N);
    dist2[P + N] = 0;
    
    while (!q2.empty()) {
        int v = q2.front();
        q2.pop();
        
        for (int u : rev_graph[v]) {
            if (dist2[u] == -1) {
                dist2[u] = dist2[v] + 1;
                q2.push(u);
            }
        }
    }
    
    // Step 5: Process queries
    for (int i = 0; i < Q; i++) {
        int K = G[i];
        int count = 0;
        
        for (int j = 0; j < N; j++) {
            // Check if we can reach node j from P in exactly K steps
            if (dist1[j] != -1 && dist1[j] <= K && (dist1[j] == K || (cycle_len1 != INT_MAX && (K - dist1[j]) % cycle_len1 == 0))) {
                count++;
            }
            
            // Check if we can reach node j from P+N in exactly K steps
            if (dist2[j] != -1 && dist2[j] <= K && (dist2[j] == K || (cycle_len2 != INT_MAX && (K - dist2[j]) % cycle_len2 == 0))) {
                count++;
            }
        }
        
        answer(count);
    }
}

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