Submission #242666

#	Time	Username	Problem	Language	Result	Execution time	Memory
242666		johutha	Tropical Garden (IOI11_garden)	C++17	0 / 100	6 ms	768 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

struct graph
{
	int n;
	int h;
	vector<vector<int>> adjlist;
	vector<vector<int>> best;
	vector<int> dist;
	vector<bool> cycle;
	int cyc = 3*n;
	int p;

	void add(int fr, int to)
	{
		int t = to;
		if (fr == best[to][0]) t += h;
		if (best[fr][0] == to)
		{
			adjlist[fr].push_back(t);
		}
		if (best[fr][1] == to)
		{
			adjlist[fr + h].push_back(t);
		}
	}

	graph(int in, int m, vector<vector<int>> ib, int R[][2]) : n(2*in), h(in), adjlist(vector<vector<int>>(2*n)), best(ib), dist(n, -1), cycle(n)
	{
		for (int i = 0; i < m; i++)
		{
			add(R[i][0], R[i][1]);
			add(R[i][1], R[i][0]);
		}
	}

	void print()
	{
		cout << n << "\n";

		for (int i = 0; i < n; i++)
		{
			for (auto j : adjlist[i])
			{
				cout << i << " " << j << "\n";
			}
		}
	}

	void reverse()
	{
		vector<vector<int>> old(n);
		swap(old, adjlist);

		for (int i = 0; i < n; i++)
		{
			for (int j : old[i])
			{
				adjlist[j].push_back(i);
			}
		}
	}

	bool dfs(int curr, int d)
	{
		if (curr == p && dist[curr] != -1)
		{
			cyc = d;
			return true;
		}
		dist[curr] = d;

		for (auto next : adjlist[curr])
		{
			if (dfs(next, d + 1)) cycle[curr] = true;
		}

		return cycle[curr];
	}
	
	void calc(int P)
	{
		p = P;
		dfs(p, 0);
	}

	void pcyc()
	{
		cout << "Cycle: " << cyc << "\n";
		for (int i = 0; i < n; i++)
		{
			cout << (i % h);
			if (i >= h) cout << "*";
			else cout << " ";
			cout << ": ";
			cout << cycle[i] << "   " << dist[i] << "\n";
		}
	}

	vector<vector<int>> lkup;
	vector<int> ncyc;

	void precheck()
	{
		lkup.resize(cyc);
		ncyc.resize(2*n);

		for (int i = 0; i < h; i++)
		{
			if (dist[i] == -1) continue;
			if (cycle[i]) lkup[dist[i] % cyc].push_back(dist[i]);
			else ncyc[dist[i]]++;
		}
		for (int i = 0; i < cyc; i++) sort(lkup[i].begin(), lkup[i].end());
	}

	int check(int t)
	{
		int tm = t % cyc;
		int r = 0;
		if (t < 2*n) r += ncyc[t];
		r += upper_bound(lkup[tm].begin(), lkup[tm].end(), t) - lkup[tm].begin();
		return r;
	}
};

void count_routes(int n, int m, int P, int R[][2], int Q, int G[])
{
	vector<vector<int>> best(n, vector<int>(2, -1));

	auto ins = [&](int k, int v)
	{
		swap(best[k][0], best[k][1]);
		best[k][0] = v;
	};

	for (int i = m - 1; i >= 0; i--)
	{
		ins(R[i][0], R[i][1]);
		ins(R[i][1], R[i][0]);
	}

	for (int i = 0; i < n; i++) if (best[i][1] == -1) best[i][1] = best[i][0];

	graph g(n, m, best, R);
	g.reverse();
	graph g2(g);
	g.calc(P);
	g2.calc(P + n);
	g.precheck();
	g2.precheck();
	
	for (int c = 0; c < Q; c++)
	{
		answer(g.check(G[c]) + g2.check(G[c]));
	}
}

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