Submission #1249007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249007		eysbutno	Tropical Garden (IOI11_garden)	C++20	0 / 100	1 ms	584 KiB

garden

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

using ll = long long;

constexpr ll INF = 1e18;

void count_routes(int n, int m, int p, int r[][2], int q, int g[]) {
    std::vector<std::vector<std::array<int, 2>>> adj(n), rev(n);
	for (int i = 0; i < m; i++) {
		adj[r[i][0]].push_back({r[i][1], i});
		adj[r[i][1]].push_back({r[i][0], i});
	}

	for (int i = 0; i < n; i++) {
		if (adj[i].size() > 2) adj[i].resize(2);
		for (const auto &[j, w] : adj[i]) {
			rev[j].push_back({i, w});
		}
	}

	std::vector<std::array<ll, 2>> dist(n, {INF, INF});
	std::vector<std::array<ll, 2>> to_p(n, {INF, INF});
	for (int tt = 0; tt < 2; tt++) {
		// t = 0 means we take best edge from p
		// t = 1 means we don't take best edge 
		if (tt == 1 && adj[p].size() == 1) break;

		std::queue<std::array<ll, 3>> bfs;
		bfs.push({0, p, tt});
		while (!bfs.empty()) {
			const auto [t, u, f] = bfs.front();
			bfs.pop();
			if (dist[u][f] != INF) continue;
			dist[u][f] = t;

			int wt = adj[u][0][1];
			for (const auto &[j, w] : rev[u]) {
				if (f == 0 && w == wt && adj[u].size() > 1) continue;
				if (f == 1 && w != wt && adj[u].size() > 1) continue;
				int flag = w != adj[j][0][1];
				bfs.push({t + 1, j, flag});
			}
		}

		for (int i = 0; i < n; i++) {
			to_p[i][tt] = dist[i][0];
		}

		dist.assign(n, {INF, INF});
	}

    ll cycle_len = 0, node = p, flag = 0;
    std::vector<std::array<bool, 2>> vis(n);
    while (!vis[node][flag]) {
        vis[node][flag] = true;

        const auto [nxt, wt] = adj[node][flag];
        if (adj[nxt].size() == 1) {
            node = nxt, flag = 0;
        } else {
            node = nxt, flag = (adj[nxt][0][1] == wt);
        }

        cycle_len++;
    }

    if (node != p) cycle_len = INF;

	for (int t = 0; t < q; t++) {
		int k = g[t], res = 0;
		for (int i = 0; i < n; i++) {
            if (to_p[i][0] <= k && ((k - to_p[i][0]) % cycle_len == 0)) {
                res++;
            } else if (to_p[i][1] <= k && ((k - to_p[i][1]) % cycle_len == 0)) {
                res++;
            }
		}

		answer(res);
	}
}

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