Submission #1162679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162679		spongb	Tropical Garden (IOI11_garden)	C++20	0 / 100	5094 ms	320 KiB

garden

#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
vector<int> succ, dist1, dist2;
int cycle_len1, cycle_len2;
vector<vector<int>> revGraph;

void find_cycle_length(int start, int& cycle_length) {
    // Initialize cycle length to a large value
    cycle_length = 1e9 + 1;
    
    // Initialize tortoise and hare pointers
    int tortoise = start;
    int hare = succ[start];
    
    // Phase 1: Find meeting point inside the cycle
    while (tortoise != hare && hare != -1) {
        tortoise = succ[tortoise];
        hare = succ[hare];
        if (hare != -1) {
            hare = succ[hare];
        }
    }
    
    // If hare reached end (no cycle) or is -1, return
    if (hare == -1) {
        return;
    }
    
    // Phase 2: Find the start of the cycle
    tortoise = start;
    while (tortoise != hare) {
        tortoise = succ[tortoise];
        hare = succ[hare];
    }
    
    // Phase 3: Measure the cycle length
    int cycle_start = tortoise;
    cycle_length = 1;
    tortoise = succ[tortoise];
    
    while (tortoise != cycle_start) {
        cycle_length++;
        tortoise = succ[tortoise];
    }
}

void dfs(int v, int d, vector<int> &dist){
    if(dist[v] != -1) return;
    
    dist[v] = d;
    
    for(int u: revGraph[v]){
        dfs(u, d+1, dist);
    }
}


void count_routes(int N, int M, int P, int ed[][2], int q, int qry[]) {
    vector<int> most_beautiful(N, -1);
    vector<int> second_most_beautiful(N, -1);
    
    for(int i = 0 ; i < M; i++){    
        int u = ed[i][0];
        int v = ed[i][1]; 
        
        if(most_beautiful[u] == -1) most_beautiful[u] = v;
        else if(second_most_beautiful[u] == -1) second_most_beautiful[u] = v;   
        if(most_beautiful[v] == -1) most_beautiful[v] = u;
        else if(second_most_beautiful[v] == -1) second_most_beautiful[v] = u;
    }
  
    for(int i = 0; i < N; i++){
        if(second_most_beautiful[i] == -1) second_most_beautiful[i] = most_beautiful[i];
    }
    
    succ.resize(2*N, -1);
    for(int i = 0; i < N; i++){
        int f = most_beautiful[i];
        int s = second_most_beautiful[i];
        
        if(most_beautiful[f] == i){
            succ[i] = f + N;
        } else succ[i] = f;
        
        if(most_beautiful[s] == i){
            succ[i + N] = s + N;
        } else succ[i + N] = s;
    }

    //find cycle length
    find_cycle_length(P, cycle_len1);
    find_cycle_length(P + N, cycle_len2);
    
    revGraph.resize(2*N, vector<int>());
    for(int i = 0; i < 2*N; i++){
        if(succ[i] != -1) revGraph[succ[i]].push_back(i);
    }
   
    dist1.assign(2*N, -1);
    dfs(P, 0, dist1);
   
    dist2.resize(2*N, -1);
    dfs(P+N, 0, dist2);
    
    int ans = 0;
    for(int i = 0; i < q; i++){
        int K = qry[i];
        int ways = 0;
        
        for(int j = 0; j < N; j++){
            if(dist1[j] == K) ways++;
            else if(cycle_len1 != 1e9+1 && dist1[j] != -1 && dist1[j] < K && ((K - dist1[j]) % cycle_len1 == 0)) ways++;
            
            if(dist2[j] == K) ways++;
            else if(cycle_len2 != 1e9+1 && dist2[j] != -1 && dist2[j] < K && ((K - dist2[j]) % cycle_len2 == 0)) ways++;
        }
        
        answer(ways);
    }
}

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