Submission #375057

#	Time	Username	Problem	Language	Result	Execution time	Memory
375057		thiago4532	Tropical Garden (IOI11_garden)	C++17	Compilation error	0 ms	0 KiB

garden

#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 2 * 110000 + 10;
vector<int> grafo[maxn];
int n, m, f[maxn][2], x[maxn];
int p, k;
bool mark[maxn];
stack<int> st, cycle;
vector<int> mod[maxn][2];
int eh_ciclo[2];

inline void build_reverse_graph() {
    for (int i = 0; i < 2*n; i++)
        grafo[ x[i] ].push_back(i);
}

bool dfs(int u, int aux) {
    mark[u] = 1;
    st.push(u);

    int v = x[u];
    if (v == aux) {
        while (!st.empty() && st.top() != aux) {
            cycle.push(st.top());
            st.pop();
        }
        if (!st.empty()) cycle.push(st.top()), st.pop();
        return true;
    }

    if (mark[v])
        return false;

    return dfs(v, aux);
}

int check_cycle(int p) {
    while (!st.empty()) st.pop();
    while (!cycle.empty()) cycle.pop();
    for (int i = 0; i < 2*n; i++)
        mark[i] = 0;

    return (dfs(p, p) ? cycle.size() : 0);
}

map<int, int> ans[2];
int dist[maxn];
void bfs(int u) {
    for (int i = 0; i < 2*n; i++)
        dist[i] = 0x3f3f3f3f, mark[i] = 0;

    queue<int> fila;
    fila.push(u);
    dist[u] = 0;

    while (!fila.empty()) {
        int u = fila.front();
        fila.pop();
        if (mark[u]) continue;
        mark[u] = true;

        if (u < n)
            ans[k][ dist[u] ]++;

        for (auto v : grafo[u]) {
            if (dist[v] > dist[u] + 1) {
                dist[v] = dist[u] + 1;
                fila.push(v);
            }
        }
    }
}

int main() {
    memset(f, -1, sizeof f);
    cin >> n >> m;
    cin >> p;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        if (f[a][0] == -1) f[a][0] = b;
        else if (f[a][1] == -1) f[a][1] = b;

        if (f[b][0] == -1) f[b][0] = a;
        else if (f[b][1] == -1) f[b][1] = a;
    }
    for (int u = 0; u < n; u++) {
        if (f[u][1] == -1) f[u][1] = f[u][0];

        int v = f[u][0];
        if (f[v][0] == u)
            x[u] = v+n;
        else
            x[u] = v;
    }
    for (int u = n; u < 2*n; u++) {
        int u_ = u - n;

        int v = f[u_][1];
        if (f[v][0] == u_)
            x[u] = v+n;
        else
            x[u] = v;
    }

    //for (int i = 0; i < 2*n; i++)
        //cout << (i < n ? i : i-n) << (i < n ? " " : "' ")  << (x[i] < n ? x[i] : x[i]-n)
             //<< (x[i] < n ? "\n" : "'\n");

    build_reverse_graph();
    eh_ciclo[0] = check_cycle(p);
    eh_ciclo[1] = check_cycle(p+n);

    bfs(p);
    k++;
    bfs(p+n);
    for (int l = 0; l < 2; l++) {
        if (eh_ciclo[l]) {
            for (auto & e : ans[l])
                mod[e.first%eh_ciclo[l]][l].push_back(e.first);
        }
    }

    int q;
    cin >> q;

    while(q--) {
        int g;
        cin >> g;

        int resp = 0;
        for (int l = 0; l < 2; l++) {
            if (eh_ciclo[l]) {
                for (auto& e : mod[g][l])
                    if (g >= e) resp += ans[l][e];
            } else
                resp += ans[l][g];
        }
        cout << resp << '\n';
    }
    return 0;
}

Compilation message (stderr)

/tmp/ccWfXQCL.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccnX9djR.o:garden.cpp:(.text.startup+0x0): first defined here
/tmp/ccWfXQCL.o: In function `main':
grader.cpp:(.text.startup+0x3b): undefined reference to `count_routes(int, int, int, int (*) [2], int, int*)'
collect2: error: ld returned 1 exit status