Submission #1126218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126218		fonikos01	Tropical Garden (IOI11_garden)	C++20	0 / 100	4 ms	5184 KiB

garden

#include <bits/stdc++.h>
#include <vector>
#include "garden.h"
#include "gardenlib.h"

using namespace std;

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
        vector<int> ans(Q);
        vector<vector<int>> g(N, vector<int>(0));
        for (int i = 0; i < M; i++)
        {
                g[R[i][0]].push_back(R[i][1]);
                g[R[i][1]].push_back(R[i][0]);
        }

        vector<int> nodesComponent(N, -1);
        vector<vector<int>> DP(N, vector<int>(2, -1));

        int timer = -1;
        int cycSz = -1;
        auto dfs = [&](auto self, int node, int prevNode) -> void
        {
                timer++;
                int state = 0, nextNode = g[node][0];
                if (g[node][0] == prevNode && g[node].size() >= 2)
                {
                        state = 1;
                        nextNode = g[node][1];
                }
                if (DP[node][state] != -1)
                {
                        if (node == P)
                                cycSz = DP[node][state] - timer;
                        return;
                }
                DP[node][state] = timer;
                self(self, nextNode, node);
                return;
        };

        dfs(dfs, P, -1);

        DP.clear();
        DP.resize(N, vector<int>(2, -2));

        auto prop = [&](auto self, int node, int prevNode) -> int
        {
                int state = 0, nextNode = g[node][0];
                if (g[node][0] == prevNode && g[node].size() >= 2)
                {
                        state = 1;
                        nextNode = g[node][1];
                }
                if (DP[node][state] != -2)
                {
                        return DP[node][state];
                }
                DP[node][state] = -1;
                DP[node][state] = self(self, nextNode, node);
                return DP[node][state];
        };

        for (int i = 0; i < N; i++)
        {
                prop(prop, i, -1);
        }

        vector<pair<int, int>> bfs = {{P, -1}};
        vector<set<int>> fromNeiVis(N);
        fromNeiVis[P].insert(-1);
        int step = 0, round = 0;
        vector<vector<int>> psVals(2e5, vector<int>(0));
        while (!bfs.empty())
        {
                vector<pair<int, int>> newbfs(0);

                for (auto [node, prevNode] : bfs)
                {
                        int state = 1;
                        if (g[node][0] == prevNode || prevNode == -1)
                        {
                                state = 0;
                        }

                        if (state == 0)
                        {
                                if (psVals[step].size() == round)
                                {
                                        psVals[step].push_back(0);
                                        if (round > 0)
                                                psVals[step][round] += psVals[step][round - 1];
                                }
                                psVals[step][round]++;
                        }
                        for (auto nei : g[node])
                        {
                                if (fromNeiVis[nei].count(node))
                                        continue;
                                fromNeiVis[nei].insert(node);
                                newbfs.push_back(make_pair(nei, node));
                        }
                }
                step++;
                if (step == cycSz)
                {
                        step = 0;
                        round++;
                }
                bfs = newbfs;
        }

        for (int i = 0; i < Q; i++)
        {
                if (cycSz == -1 && G[i] < 2e5)
                        ans[i] = psVals[G[i]][0];
                else if (cycSz != -1)
                {
                        int dCnt = G[i] / cycSz;
                        int rem = G[i] % cycSz;
                        dCnt = min(dCnt, int(psVals[rem].size()) - 1);
                        ans[i] = psVals[rem][dCnt];
                }
                answer(ans[i]);
        }
}

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