oj.uz

Submission #1063307

# Submission time Handle Problem Language Result Execution time Memory
1063307 2024-08-17T16:42:24 Z Boas Tropical Garden (IOI11_garden) C++17
100 / 100
 2567 ms 72744 KB 
#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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 904 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 708 KB Output is correct
9 Correct 2 ms 860 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 904 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 708 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 12 ms 10156 KB Output is correct
12 Correct 26 ms 16680 KB Output is correct
13 Correct 43 ms 44008 KB Output is correct
14 Correct 91 ms 57456 KB Output is correct
15 Correct 93 ms 58308 KB Output is correct
16 Correct 71 ms 40468 KB Output is correct
17 Correct 63 ms 34308 KB Output is correct
18 Correct 26 ms 16696 KB Output is correct
19 Correct 88 ms 57400 KB Output is correct
20 Correct 90 ms 58224 KB Output is correct
21 Correct 70 ms 40284 KB Output is correct
22 Correct 60 ms 34300 KB Output is correct
23 Correct 92 ms 63864 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 904 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 708 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 12 ms 10156 KB Output is correct
12 Correct 26 ms 16680 KB Output is correct
13 Correct 43 ms 44008 KB Output is correct
14 Correct 91 ms 57456 KB Output is correct
15 Correct 93 ms 58308 KB Output is correct
16 Correct 71 ms 40468 KB Output is correct
17 Correct 63 ms 34308 KB Output is correct
18 Correct 26 ms 16696 KB Output is correct
19 Correct 88 ms 57400 KB Output is correct
20 Correct 90 ms 58224 KB Output is correct
21 Correct 70 ms 40284 KB Output is correct
22 Correct 60 ms 34300 KB Output is correct
23 Correct 92 ms 63864 KB Output is correct
24 Correct 2 ms 344 KB Output is correct
25 Correct 223 ms 10228 KB Output is correct
26 Correct 407 ms 16948 KB Output is correct
27 Correct 1409 ms 44172 KB Output is correct
28 Correct 1888 ms 57688 KB Output is correct
29 Correct 1990 ms 58248 KB Output is correct
30 Correct 1182 ms 40380 KB Output is correct
31 Correct 1777 ms 34808 KB Output is correct
32 Correct 791 ms 16760 KB Output is correct
33 Correct 1829 ms 57648 KB Output is correct
34 Correct 1931 ms 58408 KB Output is correct
35 Correct 2102 ms 40328 KB Output is correct
36 Correct 1672 ms 34556 KB Output is correct
37 Correct 1702 ms 63680 KB Output is correct
38 Correct 2567 ms 72744 KB Output is correct