oj.uz

Submission #763452

# Submission time Handle Problem Language Result Execution time Memory
763452 2023-06-22T10:09:59 Z boris_mihov Tropical Garden (IOI11_garden) C++17
49 / 100
 57 ms 22376 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 ((k - j) % (cycle[fromMAX].first + cycle[fromMAX ^ 1].first) == 0 || (k - j) % (cycle[fromMAX].first + cycle[fromMAX ^ 1].first) == cycle[fromMAX].first)
                {
                    ans += cnt[j][fromMAX];
                    continue;
                }
            }
        }

        answer(ans);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4296 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 4380 KB Output is correct
7 Correct 2 ms 4040 KB Output is correct
8 Correct 2 ms 4180 KB Output is correct
9 Correct 3 ms 4408 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4296 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 4380 KB Output is correct
7 Correct 2 ms 4040 KB Output is correct
8 Correct 2 ms 4180 KB Output is correct
9 Correct 3 ms 4408 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 6952 KB Output is correct
13 Correct 32 ms 22376 KB Output is correct
14 Correct 41 ms 12068 KB Output is correct
15 Correct 57 ms 12412 KB Output is correct
16 Correct 45 ms 11676 KB Output is correct
17 Incorrect 43 ms 11284 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4296 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 4380 KB Output is correct
7 Correct 2 ms 4040 KB Output is correct
8 Correct 2 ms 4180 KB Output is correct
9 Correct 3 ms 4408 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 6952 KB Output is correct
13 Correct 32 ms 22376 KB Output is correct
14 Correct 41 ms 12068 KB Output is correct
15 Correct 57 ms 12412 KB Output is correct
16 Correct 45 ms 11676 KB Output is correct
17 Incorrect 43 ms 11284 KB Output isn't correct
18 Halted 0 ms 0 KB -