제출 #263338

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
263338		Berted	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	100 / 100	234 ms	58616 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <vector>
#include <assert.h>
#include <iostream>
#include <algorithm>
#define vi vector<int>

const int INF = 1e9;

using namespace std;

vi sadj[150001], adj[300001];
int dst[2][300001], cyc[2];
vi ans[2][300001];

void DFS(int u, int id)
{
	// cout << u << " " << id << " " << dst[id][u] << "\n";
	for (auto v : adj[u])
	{
		if (dst[id][v] == INF)
		{
			dst[id][v] = dst[id][u] + 1;
			DFS(v, id);
		}
		else 
		{
			assert(cyc[id] == -1 && dst[id][v] == 0);
			cyc[id] = dst[id][u] + 1;
		}
	}
}

/*
	It is possible to represent the problem as a digraph with 2N nodes
	such that each node has at most one outgoing edge.
	We can use this property to determine which cycle lengths are valid.
*/

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	for (int i = 0; i < M; i++)
	{
		sadj[R[i][0]].push_back(R[i][1]);
		sadj[R[i][1]].push_back(R[i][0]);
	}
	cyc[0] = cyc[1] = -1;
	for (int u = 0; u < N; u++)
	{
		for (int j = 0; j < min(2, (int)sadj[u].size()); j++)
		{
			int v = sadj[u][j];
			//cout << "Add edge " << 2 * u + j << " -> " << 2 * v + (sadj[v].size() > 1 && u == sadj[v][0]) << "\n";
			adj[2 * v + (sadj[v].size() > 1 && u == sadj[v][0])].push_back(2 * u + j);
		}
	}
	for (int i = 0; i < 2 * N; i++) {dst[0][i] = dst[1][i] = INF;}
	for (int i = 0; i < 2; i++)
	{
		dst[i][2 * P + i] = 0;
		DFS(2 * P + i, i);
		if (cyc[i] == -1)
		{
			for (int j = 0; j < 2 * N; j += 2)
			{
				if (dst[i][j] < INF) ans[i][0].push_back(dst[i][j]);
			}
			sort(ans[i][0].begin(), ans[i][0].end());
		}
		else
		{
			for (int j = 0; j < 2 * N; j += 2)
			{
				if (dst[i][j] < INF) ans[i][dst[i][j] % cyc[i]].push_back(dst[i][j]);
			}
			for (int j = 0; j < cyc[i]; j++)
			{
				sort(ans[i][j].begin(), ans[i][j].end());
			}
		}
	}
	for (int i = 0; i < Q; i++)
	{
		int ret = 0;
		for (int j = 0; j < 2; j++)
		{
			if (cyc[j] == -1)
			{
				ret += upper_bound(ans[j][0].begin(), ans[j][0].end(), G[i]) - lower_bound(ans[j][0].begin(), ans[j][0].end(), G[i]);
			}
			else
			{
				int v = G[i] % cyc[j];
				ret += upper_bound(ans[j][v].begin(), ans[j][v].end(), G[i]) - ans[j][v].begin();
			}
		}
		answer(ret);
	}
}

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