Submission #375075

#	Time	Username	Problem	Language	Result	Execution time	Memory
375075		thiago4532	Tropical Garden (IOI11_garden)	C++17	49 / 100	114 ms	48108 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.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);
            }
        }
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    memset(f, -1, sizeof f);
    n = N, m = M;
    p = P;

    for (int i = 0; i < m; i++) {
        int a, b;
        a = R[i][0], b = R[i][1];

        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);
        }
    }

    for (int i = 0 ; i < Q; i++) {
        int g = G[i];

        int resp = 0;
        for (int l = 0; l < 2; l++) {
            if (eh_ciclo[l]) {
                for (auto& e : mod[g%eh_ciclo[l]][l])
                    if (g >= e) resp += ans[l][e];
            } else
                resp += ans[l][g];
        }
        answer(resp);
    }

}



//int main() {
    //return 0;
//}

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