Submission #364191

#	Time	Username	Problem	Language	Result	Execution time	Memory
364191		b23v	Tropical Garden (IOI11_garden)	C++14	49 / 100	5056 ms	3468 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;
	}
};

bool path(int u, int v, int n, int k, const Graph<Node>& graph)
{
	Graph<int> visited(n, vi(2, -1));
	bool cycle = false;
	int t = -1, i = 0;
	while(k--)
	{
		if(graph[u][0].i == t && graph[u].size() > 1)
		{
			if(!cycle && visited[u][0] != -1)
			{
				// cycle
				int length = i - visited[u][0];
				k = min(k, k % length);
				cycle = true;
			}
			visited[u][0] = i;
			t = graph[u][1].i;
			u = graph[u][1].v;
		} else 
		{
			if(!cycle && visited[u][1] != -1)
			{
				// cycle
				int length = i - visited[u][1];
				k = min(k, k % length);
				cycle = true;
			}

			visited[u][1] = i;
			t = graph[u][0].i;
			u = graph[u][0].v;
		}
		++i;
	}
	return u == v;
}

// self loops ?
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	if(Q != 1) abort();

	Graph<Node> graph(N);
	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());

	int r = 0;
	for(int i = 0; i < N; ++i)
	{
		if(path(i, P, N, G[0], graph)) ++r;
	}
	answer(r);
}

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