oj.uz

Submission #763455

# Submission time Handle Problem Language Result Execution time Memory
763455 2023-06-22T10:12:23 Z boris_mihov Tropical Garden (IOI11_garden) C++17
100 / 100
 4317 ms 24780 KB 
#include "garden.h"
#include "gardenlib.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 150000 + 10;
const int INF  = 1e9;

int n, m, p, q;
int dp[MAXN][2];
int cnt[MAXN][2];
std::vector <std::pair <int,int>> g[MAXN];
bool vis[MAXN][2];

void dfs(int node, bool next, int edges, bool firstEdge)
{
    if (next == false)
    {
        cnt[edges][firstEdge]++;
    }

    int l = 0, r = g[node].size();
    if (next || g[node].size() == 1)
    {
        r = 1;
    } else
    {
        l = 1;
    }

    for (int i = l ; i < r ; ++i)
    {
        auto [u, t] = g[node][i];
        if (u == p)
        {
            continue;
        }

        if (t == g[u][0].second)
        {
            dfs(u, 0, edges + 1, firstEdge);
            continue;
        }

        if (t == g[u][1].second)
        {
            dfs(u, 1, edges + 1, firstEdge);
            continue;
        }
    }
}

std::pair <int,int> dfsCycle(int node, bool fromMAX, int time)
{
    if (time != 0 && node == p)
    {
        return {time, fromMAX};
    }

    if (vis[node][fromMAX])
    {
        return {-1, -1};
    }

    vis[node][fromMAX] = true;
    if (!fromMAX || g[node].size() == 1)
    {
        return dfsCycle(g[node][0].first, (g[node][0].second == g[g[node][0].first][0].second), time + 1);
    } else
    {
        return dfsCycle(g[node][1].first, (g[node][1].second == g[g[node][1].first][0].second), time + 1);
    }
}

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

    for (int i = 0 ; i < m ; ++i)
    {
        g[R[i][0] + 1].push_back({R[i][1] + 1, i + 1});
        g[R[i][1] + 1].push_back({R[i][0] + 1, i + 1});
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        std::sort(g[i].begin(), g[i].end(), [&](auto a, auto b)
        {
            return a.second < b.second;
        });
    }

    cnt[0][0]++;
    vis[p][0] = vis[p][1] = true;
    for (const auto &[u, t] : g[p])
    {
        if (t == g[u][0].second)
        {
            dfs(u, 0, 1, (t == g[p][0].second));
            continue;
        } 

        if (t == g[u][1].second)
        {
            dfs(u, 1, 1, (t == g[p][0].second));
            continue;
        }
    }
    
    std::pair <int,int> cycle[2];
    memset(vis, false, sizeof(vis));
    cycle[0] = dfsCycle(p, 0, 0);

    memset(vis, false, sizeof(vis));
    cycle[1] = dfsCycle(p, 1, 0);

    for (int i = 0 ; i < q ; ++i)
    {
        int k = G[i];
        int ans = 0;

        for (int fromMAX = 0 ; fromMAX < 2 ; ++fromMAX)
        {
            for (int j = 0 ; j <= std::min(n, k) ; ++j)
            {
                if (j == k)
                {
                    ans += cnt[j][fromMAX];
                    continue;
                }

                if (cycle[fromMAX].first == -1)
                {
                    continue;
                }

                if (j + cycle[fromMAX].first == k)
                {
                    ans += cnt[j][fromMAX];
                    continue;
                }

                if (cycle[fromMAX].second == fromMAX)
                {
                    if ((k - j) % cycle[fromMAX].first == 0)
                    {
                        ans += cnt[j][fromMAX];
                    }

                    continue;
                }

                if (cycle[fromMAX ^ 1].first == -1)
                {
                    continue;
                }

                if (cycle[fromMAX ^ 1].second == (fromMAX ^ 1))
                {
                    if ((k - j - cycle[fromMAX].first) % cycle[fromMAX ^ 1].first == 0)
                    {
                        ans += cnt[j][fromMAX];
                    }

                    continue;
                }

                int rem = (k - j) % (cycle[fromMAX].first + cycle[fromMAX ^ 1].first);
                if (rem == 0 || rem == cycle[fromMAX].first)
                {
                    ans += cnt[j][fromMAX];
                    continue;
                }
            }
        }

        answer(ans);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 ms 4052 KB Output is correct
5 Correct 2 ms 4052 KB Output is correct
6 Correct 2 ms 4308 KB Output is correct
7 Correct 2 ms 4052 KB Output is correct
8 Correct 2 ms 4180 KB Output is correct
9 Correct 3 ms 4436 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 ms 4052 KB Output is correct
5 Correct 2 ms 4052 KB Output is correct
6 Correct 2 ms 4308 KB Output is correct
7 Correct 2 ms 4052 KB Output is correct
8 Correct 2 ms 4180 KB Output is correct
9 Correct 3 ms 4436 KB Output is correct
10 Correct 2 ms 4052 KB Output is correct
11 Correct 7 ms 5204 KB Output is correct
12 Correct 15 ms 6364 KB Output is correct
13 Correct 32 ms 21432 KB Output is correct
14 Correct 49 ms 10432 KB Output is correct
15 Correct 50 ms 10720 KB Output is correct
16 Correct 42 ms 10148 KB Output is correct
17 Correct 41 ms 9712 KB Output is correct
18 Correct 14 ms 6844 KB Output is correct
19 Correct 38 ms 12108 KB Output is correct
20 Correct 46 ms 12392 KB Output is correct
21 Correct 44 ms 11372 KB Output is correct
22 Correct 54 ms 10956 KB Output is correct
23 Correct 41 ms 12676 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 ms 4052 KB Output is correct
5 Correct 2 ms 4052 KB Output is correct
6 Correct 2 ms 4308 KB Output is correct
7 Correct 2 ms 4052 KB Output is correct
8 Correct 2 ms 4180 KB Output is correct
9 Correct 3 ms 4436 KB Output is correct
10 Correct 2 ms 4052 KB Output is correct
11 Correct 7 ms 5204 KB Output is correct
12 Correct 15 ms 6364 KB Output is correct
13 Correct 32 ms 21432 KB Output is correct
14 Correct 49 ms 10432 KB Output is correct
15 Correct 50 ms 10720 KB Output is correct
16 Correct 42 ms 10148 KB Output is correct
17 Correct 41 ms 9712 KB Output is correct
18 Correct 14 ms 6844 KB Output is correct
19 Correct 38 ms 12108 KB Output is correct
20 Correct 46 ms 12392 KB Output is correct
21 Correct 44 ms 11372 KB Output is correct
22 Correct 54 ms 10956 KB Output is correct
23 Correct 41 ms 12676 KB Output is correct
24 Correct 5 ms 4052 KB Output is correct
25 Correct 487 ms 5508 KB Output is correct
26 Correct 941 ms 6868 KB Output is correct
27 Correct 2032 ms 22456 KB Output is correct
28 Correct 4251 ms 12200 KB Output is correct
29 Correct 4306 ms 12516 KB Output is correct
30 Correct 2550 ms 11740 KB Output is correct
31 Correct 2438 ms 11312 KB Output is correct
32 Correct 156 ms 6944 KB Output is correct
33 Correct 4254 ms 12236 KB Output is correct
34 Correct 4317 ms 12536 KB Output is correct
35 Correct 2689 ms 11432 KB Output is correct
36 Correct 2445 ms 11080 KB Output is correct
37 Correct 4171 ms 12808 KB Output is correct
38 Correct 3492 ms 24780 KB Output is correct