Submission #1097405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097405		VectorLi	Tropical Garden (IOI11_garden)	C++17	0 / 100	5 ms	11096 KiB

garden

#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 dist[V * 2];

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

int count(int u, int k) {
    state.reset();
    fill(dist, dist + n * 2, (int) 1E9);
    dist[u] = 0;
    DFS(u);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (length[u] == 0 && dist[i] == k) {
            sum = sum + 1;
        }
        if (length[u] > 0 && k - dist[i] >= 0 && (k - dist[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][0];
        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();

    int q = Q;

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

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