Submission #364226

#	Time	Username	Problem	Language	Result	Execution time	Memory
364226		b23v	Tropical Garden (IOI11_garden)	C++14	0 / 100	2 ms	1644 KiB

garden

#include "garden.h"
#include "gardenlib.h"

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <climits>
#include <cstring>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using ii = pair<int,int>;
using vii = vector<pair<int,int>>;
using vb = vector<bool>;
template<typename T>
using Graph = vector<vector<T>>;

struct Node
{
	int v, i;
	bool operator< (const Node& a) const
	{
		return i < a.i;
	}
};

const int MXN = 150000; 
int n, p;
int dp[MXN + 5][2];
bool instack[MXN + 5][2];
Graph<Node> graph;

int cycle_length(int t)
{
	Graph<bool> visited(n, vb(2, 0));
	int steps = 0, u = p;
	do
	{
		visited[u][t] = 1;
		if(t == 0)
		{
			int v = graph[u][0].v;
			if(graph[v][0].i == graph[u][0].i) t = 1;
			else t = 0;
			u = graph[u][0].v;
		} else
		{
			int v = graph[u][1].v;
			if(graph[v][0].i == graph[u][1].i) t = 1;
			else t = 0;
			u = graph[u][1].v;
		}
		++steps;
	} while(!visited[u][t] && u != p);
	if(u == p) return steps;
	return -1;
}

int steps(int u, int i)
{
	if(u == p) return 0;
	
	if(instack[u][i])
	{
		return -2;
	}

	instack[u][i] = 1;
	
	int& r = dp[u][i];
	if(r != -1) return r;

	r = 0;
	if(i == 0 || graph[u].size() == 1)
	{
		int v = graph[u][0].v;
	
		int select = 0;	
		if(graph[v][0].i == graph[u][0].i) select = 1;

		int c = steps(graph[u][0].v, select);
		if(c == -2) r = -2;
		else r = 1 + c;
	} else
	{
		int v = graph[u][1].v;
		
		int select = 0;	
		if(graph[v][0].i == graph[u][1].i) select = 1;
		
		int c = steps(graph[u][1].v, select);
		if(c == -2) r = -2;
		else r = 1 + c;
	}
	instack[u][i] = 0;
	return r;
}

// self loops ?
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	n = N;
	p = P;
	memset(dp, -1, sizeof dp);

	graph.assign(N, vector<Node>());
	for(int i = 0; i < M; ++i)
	{
		graph[R[i][0]].push_back(Node { R[i][1], i });
		graph[R[i][1]].push_back(Node { R[i][0], i });
	}
	for(auto x: graph) sort(x.begin(), x.end());

	// two cycle lengths
//	int cycleLength = cycle_length(0);
	int cycleLength = cycle_length(1);
	for(int j = 0; j < Q; ++j) 
	{
		int r = 0;
		for(int i = 0; i < N; ++i)
		{
			if(i == p)
			{
				if(cycleLength == G[j]) ++r;
				continue;
			}

			int s = steps(i, 0);
			if(s != -2 && s <= G[j])
			{
				int left = (G[j] - s) % G[j];
				if(left == 0) ++r;
				else if(cycleLength != -1 && cycleLength == left) ++r;
			}
		}
		answer(r);
	}
}

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