oj.uz

답안 #106803

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106803 2019-04-20T14:44:50 Z luciocf 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
69 / 100
 5000 ms 28172 KB 
#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.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 13688 KB Output is correct
2 Correct 14 ms 13688 KB Output is correct
3 Correct 14 ms 13688 KB Output is correct
4 Correct 14 ms 13604 KB Output is correct
5 Correct 14 ms 13560 KB Output is correct
6 Correct 15 ms 13688 KB Output is correct
7 Correct 14 ms 13560 KB Output is correct
8 Correct 14 ms 13560 KB Output is correct
9 Correct 17 ms 13660 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 13688 KB Output is correct
2 Correct 14 ms 13688 KB Output is correct
3 Correct 14 ms 13688 KB Output is correct
4 Correct 14 ms 13604 KB Output is correct
5 Correct 14 ms 13560 KB Output is correct
6 Correct 15 ms 13688 KB Output is correct
7 Correct 14 ms 13560 KB Output is correct
8 Correct 14 ms 13560 KB Output is correct
9 Correct 17 ms 13660 KB Output is correct
10 Correct 14 ms 13624 KB Output is correct
11 Correct 26 ms 15408 KB Output is correct
12 Correct 48 ms 16988 KB Output is correct
13 Correct 65 ms 28060 KB Output is correct
14 Correct 147 ms 24060 KB Output is correct
15 Correct 184 ms 24268 KB Output is correct
16 Correct 140 ms 21336 KB Output is correct
17 Correct 135 ms 20508 KB Output is correct
18 Correct 47 ms 16640 KB Output is correct
19 Correct 151 ms 23944 KB Output is correct
20 Correct 191 ms 24300 KB Output is correct
21 Correct 149 ms 21212 KB Output is correct
22 Correct 136 ms 20892 KB Output is correct
23 Correct 145 ms 24768 KB Output is correct

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 13688 KB Output is correct
2 Correct 14 ms 13688 KB Output is correct
3 Correct 14 ms 13688 KB Output is correct
4 Correct 14 ms 13604 KB Output is correct
5 Correct 14 ms 13560 KB Output is correct
6 Correct 15 ms 13688 KB Output is correct
7 Correct 14 ms 13560 KB Output is correct
8 Correct 14 ms 13560 KB Output is correct
9 Correct 17 ms 13660 KB Output is correct
10 Correct 14 ms 13624 KB Output is correct
11 Correct 26 ms 15408 KB Output is correct
12 Correct 48 ms 16988 KB Output is correct
13 Correct 65 ms 28060 KB Output is correct
14 Correct 147 ms 24060 KB Output is correct
15 Correct 184 ms 24268 KB Output is correct
16 Correct 140 ms 21336 KB Output is correct
17 Correct 135 ms 20508 KB Output is correct
18 Correct 47 ms 16640 KB Output is correct
19 Correct 151 ms 23944 KB Output is correct
20 Correct 191 ms 24300 KB Output is correct
21 Correct 149 ms 21212 KB Output is correct
22 Correct 136 ms 20892 KB Output is correct
23 Correct 145 ms 24768 KB Output is correct
24 Correct 17 ms 13640 KB Output is correct
25 Correct 485 ms 15696 KB Output is correct
26 Correct 737 ms 17080 KB Output is correct
27 Execution timed out 5033 ms 28172 KB Time limit exceeded
28 Halted 0 ms 0 KB -