제출 #106803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
106803		luciocf	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	69 / 100	5033 ms	28172 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;

int pai_uf[maxn], peso_uf[maxn];

bool mark[maxn], mark2[maxn], inCycle[maxn];

vector<int> rev[maxn];

void init(int N)
{
	for (int i = 0; i < N; i++)
		pai_uf[i] = i, peso_uf[i] = 1; 
}

int Find(int x)
{
	if (pai_uf[x] == x) return x;
	return pai_uf[x] = Find(pai_uf[x]);
}

void Join(int x, int y)
{
	x = Find(x), y = Find(y);
	if (x == y) return;

	if (peso_uf[x] < peso_uf[y]) swap(x, y);

	pai_uf[y] = x, peso_uf[x] += peso_uf[y]; 
}

void makeGraph(int N)
{
	for (int i = 0; i < N; i++)
	{
		int u = grafo[0][i], v = grafo[1][i];
		if (u == -1 && v == -1) continue;

		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)
{
	mark2[u] = true;

	for (auto v: rev[u])
	{
		if (mark2[v]) continue;

		nivel[v] = nivel[u]+1;
		getNivel(v);
	}
}

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])
	{
		int d = (nivel[i] >= nivel[P] ? nivel[i]-nivel[P] : sz-(nivel[P]-nivel[i]));
		if (d <= K && K%sz == d%sz) return true;
	}
	else if (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 = nivel[i]-nivel[P];
		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);

	init(2*N);

	for (int i = 0; i < 2*N; i++)
		if (pai[i] != -1)
			rev[pai[i]].push_back(i), Join(i, pai[i]);

	for (int i = 0; i < 2*N; i++)
	{
		if (!mark2[i] && pai[i] != -1)
		{
			int R = getRoot(i);
			getNivel(R);
		}
	}

	int ini1=-1, fim1=-1;
	int ini2=-1, fim2=-1;
	for (int i = 0; i < 2*N; i++)
	{
		if (Find(i) == Find(P) && nivel[pai[i]] > nivel[i])
			ini1 = pai[i], fim1 = i, sz1 = nivel[pai[i]]-nivel[i]+1;

		if (Find(i) == Find(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 (Find(i) == Find(P) && check(i, P, K, 1)) ans++;
			else if (Find(i) == Find(P+N) && check(i, P+N, K, 0)) ans++;
		}

		answer(ans);
	}
}

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