Submission #1063307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063307		Boas	Tropical Garden (IOI11_garden)	C++17	100 / 100	2567 ms	72744 KiB

garden

#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define loop(x, i) for (int i = 0; i < x; i++)
#define pb push_back

// position within the cycle, -1 if not in the cycle
vi pos;
// distance to the cycle
vi dis;
// index of last parent *not* in cycle
vi entryPoint;
vi component, cycleLengths;
vvi revrs;

vvi p;
int getNthParent(int x, int k)
{
    loop(30, i)
    {
        if ((1 << i) & k)
            x = p[i][x];
    }
    return x;
}

int getDis(int a, int b)
{
    if (component[a] != component[b])
        return -1;
    int res = 0;
    if (pos[a] == -1)
    {
        if (pos[a] == pos[b])
        {
            if (entryPoint[a] == entryPoint[b] && dis[a] >= dis[b])
            {
                int k = dis[a] - dis[b];
                if (getNthParent(a, k) == b)
                    return k;
                return -1;
            }
            return -1;
        }
        res += dis[a];
        a = p[0][entryPoint[a]];
    }
    if (pos[b] == -1)
    {
        return -1;
    }
    if (component[a] != component[b])
        throw;
    int cycleLength = cycleLengths[component[a]];
    res += (pos[b] - pos[a] + cycleLength) % cycleLength;
    return res;
}

void cycleNumbering(int i, int nr)
{
    if (pos[i] != -1)
    {
        cycleLengths.pb(nr);
        return;
    }
    pos[i] = nr;
    cycleNumbering(p[0][i], nr + 1);
}

void revDFS(int i, int c)
{
    component[i] = c;
    for (int j : revrs[i])
    {
        if (component[j] == -1)
        {
            revDFS(j, c);
        }
    }
}

void DFS(int i, int c)
{
    if (component[i] != -1)
    {
        cycleNumbering(i, 0);
        return;
    }
    revDFS(i, c);
    DFS(p[0][i], c);
}

ii getEntryPoint(int i)
{
    if (entryPoint[i] != -1)
        return {entryPoint[i], dis[i]};
    if (pos[p[0][i]] != -1)
    {
        dis[i] = 1;
        entryPoint[i] = i;
        return {i, 1};
    }
    auto [j, d] = getEntryPoint(p[0][i]);
    entryPoint[i] = j;
    dis[i] = d + 1;
    return {j, d + 1};
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    vvi adj(N);
    loop(M, i)
    {
        adj[R[i][0]].pb(R[i][1]);
        adj[R[i][1]].pb(R[i][0]);
    }
    p = vvi(30, vi(2 * N));
    loop(N, i)
    {
        int j = adj[i][0];
        if (adj[j][0] == i)
            j += N;
        p[0][i] = j;
        if (adj[i].size() == 1)
        {
            p[0][i + N] = j;
        }
        else
        {
            j = adj[i][1];
            if (adj[j][0] == i)
                j += N;
            p[0][i + N] = j;
        }
    }
    for (int x = 1; x < 30; x++)
    {
        loop(2 * N, i)
        {
            int half = p[x - 1][i];
            p[x][i] = p[x - 1][half];
        }
    }

    pos = dis = entryPoint = component = vi(2 * N, -1);
    revrs = vvi(2 * N);
    loop(2 * N, i)
    {
        revrs[p[0][i]].pb(i);
    }
    int c = 0;
    loop(2 * N, i)
    {
        if (component[i] == -1)
        {
            DFS(i, c);
            c++;
        }
    }
    loop(2 * N, i)
    {
        if (pos[i] == -1 && entryPoint[i] == -1)
        {
            getEntryPoint(i);
        }
    }

    for (int i = 0; i < Q; i++)
    {
        int K = G[i];
        int cnt = 0;
        loop(N, start)
        {
            auto reachesGoal = [&](int goal) -> bool
            {
                if (component[start] != component[goal])
                    return 0;
                if (pos[goal] >= 0)
                {
                    int l = cycleLengths[component[goal]];
                    if (pos[start] >= 0)
                    {
                        return ((pos[goal] - pos[start] + l) % l) == (K % l);
                    }
                    else
                    {
                        int d = dis[start];
                        if (d > K)
                            return 0;
                        int cur = p[0][entryPoint[start]];
                        return ((pos[goal] - pos[cur] + l) % l) == ((K - d) % l);
                    }
                }
                else if (entryPoint[start] == entryPoint[goal])
                {
                    if (dis[start] == dis[goal] + K)
                    {
                        // check with euler tour
                        if (getNthParent(start, K) == goal)
                            return 1; // not always...
                    }
                }
                return 0;
            };
            if (reachesGoal(P) || reachesGoal(P + N))
                cnt++;
            // if (nthParent(start, K) % N == P) cnt++;
        }
        answer(cnt);
    }
}

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