Submission #1137239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137239		mrsmartypants	Tropical Garden (IOI11_garden)	C++20	0 / 100	2 ms	576 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;

    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;
            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: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31