Submission #106825

#	Time	Username	Problem	Language	Result	Execution time	Memory
106825		luciocf	Tropical Garden (IOI11_garden)	C++14	100 / 100	3910 ms	33256 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
 
using namespace std;
 
const int maxn = 3e5+10;
 
typedef pair<int, int> pii;
 
int grafo[2][maxn];
 
int pai[maxn], nivel[maxn], dist[2][maxn];
int sz1, sz2;
 
bool comp[maxn];
 
bool mark[maxn], mark2[maxn], inCycle[maxn];
 
vector<int> rev[maxn];
 
void makeGraph(int N)
{
	for (int i = 0; i < N; i++)
	{
		int u = grafo[0][i], v = grafo[1][i];
 
		if (v == -1)
		{
			if (grafo[0][u] == i) pai[i] = u+N;
			else pai[i] = u;
			continue;
		}
 
		if (grafo[0][u] == i && grafo[1][u] != -1) pai[i] = u+N;
		else pai[i] = u;
 
		if (grafo[0][v] == i && grafo[1][v] != -1) pai[i+N] = v+N;
		else pai[i+N] = v;
	}
}
 
int getRoot(int u)
{
	mark[u] = true;
 
	if (mark[pai[u]]) return u;
	return getRoot(pai[u]);
}
 
void getNivel(int u, int cc)
{
	mark2[u] = true, comp[u] = cc;
 
	for (auto v: rev[u])
	{
		if (mark2[v]) continue;
 
		nivel[v] = nivel[u]+1;
		getNivel(v, cc);
	}
}
 
void getCycle(int u, int fim)
{
	inCycle[u] = true;
	if (u != fim) getCycle(pai[u], fim);
}
 
void bfs(int u, bool q)
{
	memset(mark, 0, sizeof mark);
 
	queue<int> fila;
 
	fila.push(u), dist[q][u] = 0;
 
	while (!fila.empty())
	{
		int u = fila.front();
		fila.pop();
 
		for (auto v: rev[u])
		{
			if (!mark[v])
			{
				fila.push(v); mark[v] = 1;
				dist[q][v] = dist[q][u]+1;
			}
		}
	}
}
 
bool check(int i, int P, int K, bool q)
{
	int sz = (q ? sz1 : sz2);
 
	if ((inCycle[P] && inCycle[i]) || (inCycle[P] && !inCycle[i]))
	{
		int d = dist[q][i];
		if (d <= K && K%sz == d%sz) return true;
	}
	else if (dist[q][i] != -1 && !inCycle[P] && !inCycle[i])
	{
		int d = dist[q][i];
		if (d == K) return true;
	}
 
	return false;
}
 
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	memset(pai, -1, sizeof pai);
	memset(grafo, -1, sizeof grafo);
	memset(dist, -1, sizeof dist);
 
	for (int i = 0; i < M; i++)
	{
		int u = R[i][0], v = R[i][1];
 
		if (grafo[0][u] == -1) grafo[0][u] = v;
		else if (grafo[1][u] == -1) grafo[1][u] = v;
 
		if (grafo[0][v] == -1) grafo[0][v] = u;
		else if (grafo[1][v] == -1) grafo[1][v] = u;
	}
 
	makeGraph(N);
 
	for (int i = 0; i < 2*N; i++)
		if (pai[i] != -1)
			rev[pai[i]].push_back(i);

	int r = getRoot(P);
	getNivel(r, 1);

	if (!mark2[P+N])
	{
		r = getRoot(P+N);
		getNivel(r, 0);
	}
 
	int ini1 = -1, fim1 = -1;
	int ini2 = -1, fim2 = -1;

	for (int i = 0; i < 2*N; i++)
	{
		if (comp[i] == comp[P] && nivel[pai[i]] > nivel[i])
			ini1 = pai[i], fim1 = i, sz1 = nivel[pai[i]]-nivel[i]+1;
 
		if (comp[i] == comp[P+N] && nivel[pai[i]] > nivel[i])
			ini2 = pai[i], fim2 = i, sz2 = nivel[pai[i]]-nivel[i]+1;
	}
 
	if (ini1 != -1) getCycle(ini1, fim1); 
	if (ini2 != -1) getCycle(ini2, fim2);
 
	bfs(P, 1); bfs(P+N, 0); 
 
	for (int q = 0; q < Q; q++)
	{
		int K = G[q], ans = 0;
 
		for (int i = 0; i < N; i++)
		{
			if (comp[i] == comp[P] && check(i, P, K, 1)) ans++;
			else if (comp[i] == comp[P+N] && check(i, P+N, K, 0)) ans++;
		}
 
		answer(ans);
	}
}

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