Submission #106506

#	Time	Username	Problem	Language	Result	Execution time	Memory
106506		luciocf	Tropical Garden (IOI11_garden)	C++14	0 / 100	17 ms	504 KiB

garden

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

using namespace std;

const int maxn = 1e3+10;
const int maxm = 2e4+10;

typedef pair<int, int> pii;

int m, p, k;

bool mark[maxm], ok;

vector<pii> grafo[maxn];

void dfs(int u, int ant, int qtd)
{
	if (u == p && qtd == k)
	{
		ok = 1;
		return;
	}

	for (auto pp: grafo[u])
	{
		int v = pp.first, e = pp.second;
		if (mark[e]) continue;

		if (grafo[u].size() > 1 && abs(e-ant) == m) continue;

		mark[e] = true;
		dfs(v, e, qtd+1);
	}
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	for (int i = 0; i < M; i++)
	{
		int u = R[i][0], v = R[i][1];

		grafo[u].push_back({v, i}); grafo[v].push_back({u, i+M});
	}

	m = M, p = P, k = G[0];

	int ans = 0;
	for (int i = 0; i < N; i++)
	{
		ok = 0;
		memset(mark, 0, sizeof mark);

		dfs(i, -1, 0);

		if (ok) ans++;
	}

	answer(ans);
}

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