oj.uz

Submission #106742

# Submission time Handle Problem Language Result Execution time Memory
106742 2019-04-20T05:21:55 Z luciocf Tropical Garden (IOI11_garden) C++14
0 / 100
 5000 ms 11128 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], grau[maxn];
int sz1, sz2;

int pai_uf[maxn], peso_uf[maxn];

vector<int> rev[maxn];

bool mark[maxn], inCycle[maxn], reach[2][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 (v == -1)
		{
			pai[i] = u+N, grau[u+N]++;
			continue;
		}

		if (grafo[0][u] == i && grafo[1][u] != -1) pai[i] = u+N, grau[u+N]++;
		else pai[i] = u, grau[u]++;

		if (grafo[0][v] == i && grafo[1][v] != -1) pai[i+N] = v+N, grau[v+N]++;
		else pai[i+N] = v, grau[v]++;
	}
}

void calcNivel(int u, int lvl)
{
	if (mark[u]) return;

	nivel[u] = lvl, mark[u] = 1;
	calcNivel(pai[u], lvl+1);
}

void getCycle(int u, int fim)
{
	inCycle[u] = true;
	if (u != fim) getCycle(pai[u], fim);
}

void dfs(int u, int q)
{
	reach[q][u] = true;

	for (auto v: rev[u])
		if (!reach[q][v]) 
			dfs(v, q);
}

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

	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]);

	dfs(P, 1); dfs(P+N, 0);

	int cc = 0;
	for (int i = 0; i < 2*N; i++)
		if (grau[i] == 0)
			calcNivel(i, 0);

	int ini1, fim1;
	int ini2, fim2;
	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[i]-nivel[pai[i]]+1;

		if (Find(i) == Find(P+N) && nivel[pai[i]] < nivel[i])
			ini2 = pai[i], fim2 = i, sz2 = nivel[i]-nivel[pai[i]]+1;
	}

	getCycle(ini1, fim1); getCycle(ini2, fim2);

	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);
	}
}

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:136:6: warning: unused variable 'cc' [-Wunused-variable]
  int cc = 0;
      ^~
garden.cpp:75:2: warning: 'fim2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if (u != fim) getCycle(pai[u], fim);
  ^~
garden.cpp:142:12: note: 'fim2' was declared here
  int ini2, fim2;
            ^~~~
garden.cpp:74:13: warning: 'ini2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  inCycle[u] = true;
  ~~~~~~~~~~~^~~~~~
garden.cpp:142:6: note: 'ini2' was declared here
  int ini2, fim2;
      ^~~~
garden.cpp:75:2: warning: 'fim1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if (u != fim) getCycle(pai[u], fim);
  ^~
garden.cpp:141:12: note: 'fim1' was declared here
  int ini1, fim1;
            ^~~~
garden.cpp:74:13: warning: 'ini1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  inCycle[u] = true;
  ~~~~~~~~~~~^~~~~~
garden.cpp:141:6: note: 'ini1' was declared here
  int ini1, fim1;
      ^~~~

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11128 KB Output is correct
2 Correct 12 ms 11000 KB Output is correct
3 Execution timed out 5078 ms 11128 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11128 KB Output is correct
2 Correct 12 ms 11000 KB Output is correct
3 Execution timed out 5078 ms 11128 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11128 KB Output is correct
2 Correct 12 ms 11000 KB Output is correct
3 Execution timed out 5078 ms 11128 KB Time limit exceeded
4 Halted 0 ms 0 KB -