Submission #553353

#	Time	Username	Problem	Language	Result	Execution time	Memory
553353		timreizin	Tropical Garden (IOI11_garden)	C++17	100 / 100	2523 ms	13300 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <vector>

using namespace std;

void count_routes(int n, int m, int p, int R[][2], int q, int G[])
{
    vector<int> adj(2 * n, -1), best(n, -1);
    for (int i = 0; i < m; ++i)
    {
        auto [u, v] = R[i];
        if (best[u] == -1) best[u] = v;
        if (adj[2 * u] == -1) adj[2 * u] = v;
        else if (adj[2 * u + 1] == -1) adj[2 * u + 1] = v;
        swap(u, v);
        if (best[u] == -1) best[u] = v;
        if (adj[2 * u] == -1) adj[2 * u] = v;
        else if (adj[2 * u + 1] == -1) adj[2 * u + 1] = v;
    }
    for (int i = 0; i < n; ++i)
    {
        if (adj[2 * i + 1] == -1) adj[2 * i + 1] = adj[2 * i];
        adj[2 * i] *= 2;
        adj[2 * i + 1] *= 2;
        if (best[adj[2 * i] / 2] == i) ++adj[2 * i];
        if (best[adj[2 * i + 1] / 2] == i) ++adj[2 * i + 1];
    }
    vector<int> d(2 * n, -1);
    auto dfs = [&d, &adj](auto self, int v) -> int
    {
        if (d[v] == -2) return -3;
        if (d[v] != -1) return d[v];
        d[v] = -2;
        d[v] = self(self, adj[v]) + 1;
        if (d[v] == -2) return -3;
        return d[v];
    };
    vector<int> result(q);
    //2 * p
    d[2 * p] = 0;
    for (int i = 0; i < 2 * n; ++i) if (d[i] == -1) dfs(dfs, i);
    int len = 0;
    if (d[adj[2 * p]] > 0) len = d[adj[2 * p]] + 1;
    for (int i = 0; i < q; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (d[2 * j] >= 0 && G[i] >= d[2 * j])
            {
                if (len) result[i] += (G[i] - d[2 * j]) % len == 0;
                else result[i] += G[i] == d[2 * j];
            }
        }
    }
    //2 * p + 1
    d = vector<int>(2 * n, -1);
    d[2 * p + 1] = 0;
    for (int i = 0; i < 2 * n; ++i) if (d[i] == -1) dfs(dfs, i);
    len = 0;
    if (d[adj[2 * p + 1]] > 0) len = d[adj[2 * p + 1]] + 1;
    for (int i = 0; i < q; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (d[2 * j] >= 0 && G[i] >= d[2 * j])
            {
                if (len) result[i] += (G[i] - d[2 * j]) % len == 0;
                else result[i] += G[i] == d[2 * j];
            }
        }
    }
    for (int i : result) answer(i);
}

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