oj.uz

Submission #106827

# Submission time Handle Problem Language Result Execution time Memory
106827 2019-04-20T16:15:19 Z luciocf Tropical Garden (IOI11_garden) C++14
100 / 100
 3968 ms 33316 KB 
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
 
using namespace std;
 
const int maxn = 3e5+10;
 
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;
	}

	for (int i = 0; i < 2*N; i++)
		if (pai[i] != -1)
			rev[pai[i]].push_back(i);
}
 
int getRoot(int u)
{
	mark[u] = true;
 	
 	return (mark[pai[u]] ? u : getRoot(pai[u]));
}
 
void dfs(int u, int cc)
{
	mark2[u] = true, comp[u] = cc;
 
	for (auto v: rev[u])
	{
		if (mark2[v]) continue;
 
		nivel[v] = nivel[u]+1;
		dfs(v, cc);
	}
}

void markCycle(int u, int fim)
{
	inCycle[u] = true;

	if (u != fim) markCycle(pai[u], fim);
}

void findCycle(int N, int P)
{
	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) markCycle(ini1, fim1); 
	if (ini2 != -1) markCycle(ini2, fim2);
}
 
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);

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

	if (!mark2[P+N])
	{
		r = getRoot(P+N);
		dfs(r, 0);
	}

	findCycle(N, P);
 
	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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 13688 KB Output is correct
2 Correct 13 ms 13688 KB Output is correct
3 Correct 15 ms 13656 KB Output is correct
4 Correct 15 ms 13688 KB Output is correct
5 Correct 13 ms 13616 KB Output is correct
6 Correct 15 ms 13788 KB Output is correct
7 Correct 15 ms 13560 KB Output is correct
8 Correct 14 ms 13560 KB Output is correct
9 Correct 16 ms 13704 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 13688 KB Output is correct
2 Correct 13 ms 13688 KB Output is correct
3 Correct 15 ms 13656 KB Output is correct
4 Correct 15 ms 13688 KB Output is correct
5 Correct 13 ms 13616 KB Output is correct
6 Correct 15 ms 13788 KB Output is correct
7 Correct 15 ms 13560 KB Output is correct
8 Correct 14 ms 13560 KB Output is correct
9 Correct 16 ms 13704 KB Output is correct
10 Correct 14 ms 13560 KB Output is correct
11 Correct 23 ms 14840 KB Output is correct
12 Correct 38 ms 15768 KB Output is correct
13 Correct 61 ms 28756 KB Output is correct
14 Correct 104 ms 20732 KB Output is correct
15 Correct 185 ms 20944 KB Output is correct
16 Correct 121 ms 19228 KB Output is correct
17 Correct 120 ms 18556 KB Output is correct
18 Correct 38 ms 15736 KB Output is correct
19 Correct 99 ms 20728 KB Output is correct
20 Correct 163 ms 20932 KB Output is correct
21 Correct 131 ms 19172 KB Output is correct
22 Correct 118 ms 18424 KB Output is correct
23 Correct 95 ms 21244 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 13688 KB Output is correct
2 Correct 13 ms 13688 KB Output is correct
3 Correct 15 ms 13656 KB Output is correct
4 Correct 15 ms 13688 KB Output is correct
5 Correct 13 ms 13616 KB Output is correct
6 Correct 15 ms 13788 KB Output is correct
7 Correct 15 ms 13560 KB Output is correct
8 Correct 14 ms 13560 KB Output is correct
9 Correct 16 ms 13704 KB Output is correct
10 Correct 14 ms 13560 KB Output is correct
11 Correct 23 ms 14840 KB Output is correct
12 Correct 38 ms 15768 KB Output is correct
13 Correct 61 ms 28756 KB Output is correct
14 Correct 104 ms 20732 KB Output is correct
15 Correct 185 ms 20944 KB Output is correct
16 Correct 121 ms 19228 KB Output is correct
17 Correct 120 ms 18556 KB Output is correct
18 Correct 38 ms 15736 KB Output is correct
19 Correct 99 ms 20728 KB Output is correct
20 Correct 163 ms 20932 KB Output is correct
21 Correct 131 ms 19172 KB Output is correct
22 Correct 118 ms 18424 KB Output is correct
23 Correct 95 ms 21244 KB Output is correct
24 Correct 16 ms 13560 KB Output is correct
25 Correct 453 ms 14924 KB Output is correct
26 Correct 746 ms 15784 KB Output is correct
27 Correct 2913 ms 28784 KB Output is correct
28 Correct 3150 ms 20748 KB Output is correct
29 Correct 2894 ms 21044 KB Output is correct
30 Correct 1759 ms 19236 KB Output is correct
31 Correct 1923 ms 18524 KB Output is correct
32 Correct 542 ms 15868 KB Output is correct
33 Correct 3139 ms 20732 KB Output is correct
34 Correct 2769 ms 21052 KB Output is correct
35 Correct 1965 ms 20472 KB Output is correct
36 Correct 2603 ms 20104 KB Output is correct
37 Correct 3115 ms 22812 KB Output is correct
38 Correct 3968 ms 33316 KB Output is correct