Submission #1133097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133097		dhruv05	Tropical Garden (IOI11_garden)	C++20	Compilation error	0 ms	0 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);
}

int main(){
    cin >> N >> M >> P;

    for (int i = 0; i < M; i++ ){
        int a, b; cin >> a >> b;
        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] ++;
            }
        }
    }

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

Compilation message (stderr)

/usr/bin/ld: /tmp/ccD7ji51.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cctOiRR3.o:garden.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccD7ji51.o: in function `main':
grader.cpp:(.text.startup+0x3f): undefined reference to `count_routes(int, int, int, int (*) [2], int, int*)'
collect2: error: ld returned 1 exit status