Submission #1097410

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

garden

#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define long long long

using namespace std;

const int V = (int) 1.5E5;

int n, m, x;
vector<pair<int, int>> e[V];

int t[V];
int p[V * 2];
int d[V * 2];
bitset<V * 2> f;
vector<int> a[V * 2];

// int length[2];
int length[V * 2];

void generate() {
    queue<int> q;
    for (int i = 0; i < n * 2; i++) {
        if (d[i] == 0) {
            q.push(i);
        }
    }
    while (q.empty() == 0) {
        int u = q.front(), v = p[u];
        q.pop();
        f[u] = 1;
        d[v] = d[v] - 1;
        if (d[v] == 0) {
            q.push(v);
        }
    }
    for (int i = 0; i < n * 2; i++) {
        if (f[i] == 0) {
            vector<int> a;
            for (int u = i; f[u] == 0; u = p[u]) {
                a.push_back(u);
                f[u] = 1;
            }
            for (auto u : a) {
                length[u] = (int) a.size();
            }
        }
    }
}

bitset<V * 2> state;
int dist1[V * 2];
int dist2[V * 2];

void DFS1(int u) {
    state[u] = 1;
    for (auto v : a[u]) {
        if (state[v] == 0) {
            dist1[v] = dist1[u] + 1;
            DFS(v);
        }
    }
}

void DFS2(int u) {
    state[u] = 1;
    for (auto v : a[u]) {
        if (state[v] == 0) {
            dist2[v] = dist2[u] + 1;
            DFS(v);
        }
    }
}

int count1(int u, int k) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (length[u] == 0 && dist1[i] == k) {
            sum = sum + 1;
        }
        if (length[u] > 0 && k - dist1[i] >= 0 && (k - dist1[i]) % length[u] == 0) {
            sum = sum + 1;
        }
    }
    return sum;
}

int count2(int u, int k) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (length[u] == 0 && dist2[i] == k) {
            sum = sum + 1;
        }
        if (length[u] > 0 && k - dist2[i] >= 0 && (k - dist2[i]) % length[u] == 0) {
            sum = sum + 1;
        }
    }
    return sum;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    n = N;
    m = M;
    x = P;

    fill(t, t + n, m);
    for (int i = 0; i < m; i++) {
        int u, v;
        u = R[i][0];
        v = R[i][1];
        e[u].push_back({v, i});
        e[v].push_back({u, i});
        t[u] = min(t[u], i);
        t[v] = min(t[v], i);
    }

    for (int u = 0; u < n; u++) {
        int v, i;
        tie(v, i) = e[u][0];
        if (i != t[v]) {
            p[u] = v;
            d[v] = d[v] + 1;
            a[v].push_back(u);
        } else {
            p[u] = v + n;
            d[v + n] = d[v + n] + 1;
            a[v + n].push_back(u);
        }
        if ((int) e[u].size() > 1) {
            tie(v, i) = e[u][1];
        }
        if (i != t[v]) {
            p[u + n] = v;
            d[v] = d[v] + 1;
            a[v].push_back(u + n);
        } else {
            p[u + n] = v + n;
            d[v + n] = d[v + n] + 1;
            a[v + n].push_back(u + n);
        }
    }
    generate();

    state.reset();
    fill(dist1, dist1 + n * 2, (int) 1E9);
    dist1[x] = 0;
    DFS1(x);
    state.reset();
    fill(dist2, dist2 + n * 2, (int) 1E9);
    dist2[x + n] = 0;
    DFS2(x + n);

    int q = Q;

    for (int i = 0; i < q; i++) {
        int k = G[i];
        answer(count1(x, k) + count2(x + n, k));
        // cout << count(x, k) + count(x + n, k) << " ";
    }
}

Compilation message (stderr)

garden.cpp: In function 'void DFS1(int)':
garden.cpp:64:13: error: 'DFS' was not declared in this scope; did you mean 'DFS1'?
   64 |             DFS(v);
      |             ^~~
      |             DFS1
garden.cpp: In function 'void DFS2(int)':
garden.cpp:74:13: error: 'DFS' was not declared in this scope; did you mean 'DFS2'?
   74 |             DFS(v);
      |             ^~~
      |             DFS2