Submission #1133102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133102		dhruv05	Tropical Garden (IOI11_garden)	C++20	0 / 100	5 ms	8768 KiB

garden

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

int N, M, P; 
// trail #, child
set<pair<int, int>> edges[150000];
bool visited[150000][2] = {{false}};
vector<pair<int, int>> distances(150000, {-1, -1});
bool cycle_found = false;
bool P_found = false;
int distancel;

void dfs(int current_node, int parent){

    bool optimal = false;
    if (parent == -1 || (*edges[current_node].begin()).second != parent || edges[current_node].size() == 1){
        // will act the same way as it would if it were the starting position
        optimal = true;
        if (visited[current_node][1]){
            if (distances[current_node].second == -1){
                cycle_found = true;
            } else {
                P_found = true;
                distancel += distances[current_node].second;
            }
            return;
        } else {
            visited[current_node][1] = true;
        }
    } else {
        // parent is the best option but it cannot go there - will go to second choice
        if (visited[current_node][0]){
            if (distances[current_node].first == -1){
                cycle_found = true;
            } else {
                P_found = true;
                distancel += distances[current_node].first;
            }
            return;
        } else {
            visited[current_node][0] = true;
        }
    }
    
    if (edges[current_node].size() == 1 && parent != -1){
        distancel++;
        dfs(parent, current_node);
        return;
    }

    if (parent == -1 && edges[current_node].size() == 0){
        return;
    }

    int child;
    if (optimal){
        child = (*edges[current_node].begin()).second;
    } else {
        child = (*next(edges[current_node].begin())).second;
    }

    distancel++;
    dfs(child, current_node);
    

}

void assign(int current_node, int parent){

    bool optimal = false;
    if (parent == -1 || (*edges[current_node].begin()).second != parent || edges[current_node].size() == 1){
        // will act the same way as it would if it were the starting position
        optimal = true;
        if (distances[current_node].second != -1){
            return;
        } else {
            distances[current_node].second = distancel;
        }
    } else {
        // parent is the best option but it cannot go there - will go to second choice
        if (distances[current_node].first != -1){
            return;
        } else {
            distances[current_node].first = distancel;
        }
    }
    
    if (edges[current_node].size() == 1 && parent != -1){
        distancel--;
        assign(parent, current_node);
        return;
    }

    if (parent == -1 && edges[current_node].size() == 0){
        return;
    }

    int child;
    if (optimal){
        child = (*edges[current_node].begin()).second;
    } else {
        child = (*next(edges[current_node].begin())).second;
    }

    distancel--;
    assign(child, current_node);
}

void count_routes(int N, int M, int P, int (*R)[2], int Q, int *G){

    for (int i = 0; i < M; i++ ){
        int a = R[i][0];
        int b = R[i][1];
        edges[a].insert({i, b});
        edges[b].insert({i, a});
    }

    visited[P][0] = visited[P][1] = true;
    distances[P].first = distances[P].second = 0;

    for (int i = 0; i < N; i++ ){
        if (!visited[i][1]){
            cycle_found = false;
            P_found = false;
            distancel = 0;
            dfs(i, -1);
            if (P_found == true){
                assign(i, -1);
            }
        }
    }

    // distance to num routes exactly
    map<int, int> exactroutecount;
    for (int i = 0; i < N; i++){
        if (distances[i].second != -1){
            if (exactroutecount.find(distances[i].second) == exactroutecount.end()){
                exactroutecount[distances[i].second] = 1;
            } else {
                exactroutecount[distances[i].second] ++;
            }
        }
    }

    for (int i = 0; i < Q; i++ ){
        if (exactroutecount.find(G[i]) == exactroutecount.end()){
            cout << 0 << endl;
        } else {
            cout << exactroutecount[G[i]] << endl;
        }
    }
}

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