Submission #1162689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162689		spongb	Tropical Garden (IOI11_garden)	C++20	100 / 100	1700 ms	30000 KiB

garden

#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
int cycle_len;
vector<int> succ, color, dist, dist1, dist2;
vector<bool> visited;
vector<vector<int>> revGraph;

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


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++){   //since edges are already given in decreasing order of beauty, you can choose the earlier one 
        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;   //using if here would be a mistake it should be if else
        
        if(most_beautiful[v] == -1) most_beautiful[v] = u;
        else if(second_most_beautiful[v] == -1) second_most_beautiful[v] = u;
    }
    
    //for nodes with only since edge, they can choose the most_beautiful one again even if its used, so it becomes their second most beautiful edge too
    //this cant be applied for nodes with multiple edges when there is an alternative second edge, it should be chosen. this is why we used if/else if statements in above for loop
    //and not just use if and if directly without the need for this extra for loop. because then we'd be setting the best edge as the first best and also the second best which is wrong
    //for nodes with multiple options
    for(int i = 0; i < N; i++){
        if(second_most_beautiful[i] == -1) second_most_beautiful[i] = most_beautiful[i];
    }
    
    
    //now for each state(starting at each vertex), you exactly exactly one outgoing edge at each vertex
    //if you reached v using the its most_beautiful edge, then v should should second_most_beautiful edge to go next
    //say you used second_most_beautful[v] to reach w, and maybe that's w's most beautiful edge, so w should use its second most beautiful
    //so this is a functional graph
    
    //for every vertex v, you'll either reach v or v' (based on the path taken to reach v)
    //now v has exactly one outgoing edge
    //v' has exactly one outgoing edge
    //its a functional graph basically
    
    //build the outgoing edge for each vertex (v and v')
    succ.resize(2*N, -1);
    revGraph.assign(2 * N, vector<int>());
    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
    int cycle_len1 = 1e9 + 100, cycle_len2 = 1e9 + 100;
    
    int cur = P;
    for (int i = 0; i < 2 * N; i++) {
        cur = succ[cur];
        if (cur == P) {
            cycle_len1 = i + 1;
            break;
        }
    }
    
    cur = P + N;
    for (int i = 0; i < 2 * N; i++) {
        cur = succ[cur];
        if (cur == P + N) {
            cycle_len2 = i + 1;
            break;
        }
    }
    
    revGraph.resize(2*N);
    for(int i = 0; i < 2*N; i++){
        if(succ[i] != -1) revGraph[succ[i]].push_back(i);
    } 
    
    dist1.assign(2*N, -1);
    dfs1(P, 0, dist1, revGraph);
    
    dist2.resize(2*N, -1);
    dfs1(P+N, 0, dist2, revGraph);
    
    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: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31