oj.uz

Submission #106825

# Submission time Handle Problem Language Result Execution time Memory
106825 2019-04-20T16:05:35 Z luciocf Tropical Garden (IOI11_garden) C++14
100 / 100
 3910 ms 33256 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;
 
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.0 / 49.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 13656 KB Output is correct
2 Correct 14 ms 13688 KB Output is correct
3 Correct 15 ms 13660 KB Output is correct
4 Correct 14 ms 13660 KB Output is correct
5 Correct 13 ms 13560 KB Output is correct
6 Correct 14 ms 13688 KB Output is correct
7 Correct 14 ms 13604 KB Output is correct
8 Correct 14 ms 13560 KB Output is correct
9 Correct 15 ms 13688 KB Output is correct
10 Correct 14 ms 13560 KB Output is correct
11 Correct 22 ms 14840 KB Output is correct
12 Correct 37 ms 15760 KB Output is correct
13 Correct 62 ms 28732 KB Output is correct
14 Correct 105 ms 20696 KB Output is correct
15 Correct 164 ms 20940 KB Output is correct
16 Correct 111 ms 19224 KB Output is correct
17 Correct 122 ms 18424 KB Output is correct
18 Correct 39 ms 15784 KB Output is correct
19 Correct 103 ms 20736 KB Output is correct
20 Correct 163 ms 20832 KB Output is correct
21 Correct 162 ms 19176 KB Output is correct
22 Correct 116 ms 18544 KB Output is correct
23 Correct 98 ms 21268 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 13656 KB Output is correct
2 Correct 14 ms 13688 KB Output is correct
3 Correct 15 ms 13660 KB Output is correct
4 Correct 14 ms 13660 KB Output is correct
5 Correct 13 ms 13560 KB Output is correct
6 Correct 14 ms 13688 KB Output is correct
7 Correct 14 ms 13604 KB Output is correct
8 Correct 14 ms 13560 KB Output is correct
9 Correct 15 ms 13688 KB Output is correct
10 Correct 14 ms 13560 KB Output is correct
11 Correct 22 ms 14840 KB Output is correct
12 Correct 37 ms 15760 KB Output is correct
13 Correct 62 ms 28732 KB Output is correct
14 Correct 105 ms 20696 KB Output is correct
15 Correct 164 ms 20940 KB Output is correct
16 Correct 111 ms 19224 KB Output is correct
17 Correct 122 ms 18424 KB Output is correct
18 Correct 39 ms 15784 KB Output is correct
19 Correct 103 ms 20736 KB Output is correct
20 Correct 163 ms 20832 KB Output is correct
21 Correct 162 ms 19176 KB Output is correct
22 Correct 116 ms 18544 KB Output is correct
23 Correct 98 ms 21268 KB Output is correct
24 Correct 16 ms 13560 KB Output is correct
25 Correct 439 ms 14924 KB Output is correct
26 Correct 714 ms 15792 KB Output is correct
27 Correct 2885 ms 28796 KB Output is correct
28 Correct 3032 ms 20748 KB Output is correct
29 Correct 2878 ms 20968 KB Output is correct
30 Correct 1699 ms 19228 KB Output is correct
31 Correct 1860 ms 18520 KB Output is correct
32 Correct 524 ms 15864 KB Output is correct
33 Correct 3072 ms 20740 KB Output is correct
34 Correct 2806 ms 20940 KB Output is correct
35 Correct 1927 ms 19180 KB Output is correct
36 Correct 2499 ms 18552 KB Output is correct
37 Correct 2991 ms 21288 KB Output is correct
38 Correct 3910 ms 33256 KB Output is correct