Submission #1126502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126502		fonikos01	Tropical Garden (IOI11_garden)	C++20	100 / 100	4048 ms	20408 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<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 = timer-DP[node][state];
                        return;
                }
                DP[node][state] = timer;
                self(self, nextNode, node);
                return;
        };

        dfs(dfs, P, (g[P].size()>1?-1:g[P][0]));
        DP.clear();
        DP.resize(N, vector<int>(2, -2));
        DP[P][0] = 0;

        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;
                int step = self(self, nextNode, node);
                if (step != -1) step++;
                DP[node][state] = step;
                return DP[node][state];
        };
        for (int i = 0; i < N; i++) prop(prop, i, -1);
                

        int cnt = 0;
        // auto dfs2 = [&](auto self, int node, int prevNode, int K) -> void
        // {
        //         int state = 0;
        //         if (g[node][0] != prevNode) state = 1;
        //         if (state == 0 && DP[node][state] != -1) {
        //                 if (DP[node][state] == K || (cycSz != -1 && K > DP[node][state] && (K-DP[node][state])%cycSz == 0)) cnt++;
        //         }
        //         // cout << "node " << node << " " << state << '\n';
        //         if (vis[node][state] != -1) return;
        //         vis[node][state] = 1;
        //         if (state == 0) {
        //                 for (int i = 1; i < g[node].size(); i++) self(self, g[node][i], node, K);
        //         } else self(self, g[node][0], node, K);
        //         return;
        // };
        for (int i = 0; i < Q; i++) {
                cnt = 0;
                // vis.clear();
                // vis.resize(N, vector<int>(2, -1));
                // dfs2(dfs2, P, g[P][0], G[i]);
                for (int j = 0; j < N; j++) {
                        if (DP[j][0] == G[i] || (DP[j][0] != -1 && cycSz != -1 && G[i] > DP[j][0] && (G[i]-DP[j][0])%cycSz == 0)) cnt++;
                }
                ans[i] += cnt;
        }

        if (g[P].size() > 1) {
                DP.clear();
                DP.resize(N, vector<int>(2, -1));
                timer = 1; cycSz = -1;
                dfs(dfs, P, g[P][0]);
                DP.clear();
                DP.resize(N, vector<int>(2, -2));
                DP[P][1] = 0;
                for (int i = 0; i < N; i++) {
                        prop(prop, i, -1);
                }
                for (int i = 0; i < Q; i++) {
                        cnt = 0;
                        // vis.clear();
                        // vis.resize(N, vector<int>(2, -1));
                        // dfs2(dfs2, P, -1, G[i]);
                        for (int j = 0; j < N; j++) {
                                if (DP[j][0] == G[i] || ( DP[j][0] != -1 && cycSz != -1 && G[i] > DP[j][0] && (G[i]-DP[j][0])%cycSz == 0)) cnt++;
                        }
                        ans[i] += cnt;
                }
        }

        for (int i = 0; i < Q; i++) answer(ans[i]);
}

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