Submission #1017805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017805		Sho10	Tropical Garden (IOI11_garden)	C++17	0 / 100	22 ms	348 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <map>
#include <set>
#include <vector>

using namespace std;

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    vector<vector<int>> adj(N, vector<int>(3, 0));

    for (int i = 0; i < M; i++) {
        int a = R[i][0], b = R[i][1];
        if (adj[a][2] < 2) adj[a][adj[a][2]++] = b;
        if (adj[b][2] < 2) adj[b][adj[b][2]++] = a;
    }

    map<pair<pair<int, int>, int>, int> cycles;
    for (int i = 0; i < N; i++) {
        if (adj[i][2] == 0) continue;

        set<int> been_nmb;
        set<int> been_mb;

        int c = i;
        int got = -1;
        int ocyc = 0;
        bool got_mb = false;
        int from = -1;
        for (int a = 0;; a++) {
            if (adj[c][2] > 1 && adj[c][0] == from) {
                if (c == P) {
                    if (got == -1) got = a, got_mb = true;
                    else if (got_mb) {
                        cycles[{ { got, ocyc }, a - got }]++;
                        break;
                    } else if (!ocyc) ocyc = a - got;
                }

                if (!been_mb.insert(c).second) {
                    if (got >= 0) cycles[{ { got, ocyc }, 0 }]++;
                    break;
                }

                from = c;
                c = adj[c][1];
            } else {
                if (c == P) {
                    if (got == -1) got = a;
                    else if (!got_mb) {
                        cycles[{ { got, ocyc }, a - got }]++;
                        break;
                    } else if (!ocyc) ocyc = a - got;
                }

                if (!been_nmb.insert(c).second) {
                    if (got >= 0) cycles[{ { got, ocyc }, 0 }]++;
                    break;
                }

                from = c;
                c = adj[c][0];
            }
        }
    }

    for (int it = 0; it < Q; it++) {
        int res = 0;
        for (pair<pair<pair<int, int>, int>, int> cycle : cycles) {
            int k = G[it] - cycle.first.first.first;
            if (k >= 0 && cycle.first.second) k %= cycle.first.second;
            if (k == 0 || k == cycle.first.first.second) res += cycle.second;
        }
        answer(res);
    }
}

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