Submission #1111263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111263		codexistent	Tropical Garden (IOI11_garden)	C++14	100 / 100	83 ms	32072 KiB

garden

//testing
#include "garden.h"
#include "gardenlib.h"
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
 
int deg[150010], Mn[150010], F[300010], D[300010], n, Res[2010];
bool v[300010];
vector<int> E[300010];
 
void DFS(int a, int d){
	int i;
	D[a] = d;
	for (i = 0; i < E[a].size(); i++){
		if (D[E[a][i]] == -1) DFS(E[a][i], d + 1);
	}
}
 
int QQ, DD[300010];
struct Query{
	int a, num;
	bool operator < (const Query &p) const {
		return a < p.a;
	}
} w[2010];
 
int S[300010];
 
void Do(int a){
	int i, x, c = 0, cnt = 0, pv;
	for (i = 0; i < 2 * n; i++){
		D[i] = -1;
		v[i] = false;
		S[i] = 0;
	}
	DFS(a, 0);
	for (i = 0; i < n; i++){
		if (D[i] != -1){
			DD[cnt++] = D[i];
		}
	}
	sort(DD, DD + cnt);
	x = a;
	while (!v[x]){
		c++;
		v[x] = true;
		x = F[x];
	}
	if (x != a){
		c = 1000000009;
	}
	pv = 0;
	for (i = 0; i < QQ; i++){
		while (pv < cnt && DD[pv] <= w[i].a){
			S[DD[pv] % c]++;
			pv++;
		}
		if (w[i].a % c > 2 * n)continue;
		Res[w[i].num] += S[w[i].a % c];
	}
}
 
void Add(int a, int b, int i){
	if (Mn[a] == i){
		if (Mn[b] != i || deg[b] == 1) F[a] = b;
		else F[a] = b + n;
	}
	else if (F[a + n] == -1){
		if (Mn[b] != i || deg[b] == 1) F[a + n] = b;
		else F[a + n] = b + n;
	}
}
 
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	int i, a, b;
	n = N;
	QQ = Q;
	for (i = 0; i < Q; i++){
		w[i].a = G[i];
		w[i].num = i;
	}
	sort(w, w + Q);
	for (i = 0; i < 2 * N; i++) F[i] = -1;
	for (i = 0; i < M; i++){
		a = R[i][0], b = R[i][1];
		deg[a]++, deg[b]++;
		if (!Mn[a]) Mn[a] = i + 1;
		if (!Mn[b]) Mn[b] = i + 1;
	}
	for (i = 0; i < M; i++){
		a = R[i][0], b = R[i][1];
		Add(a, b, i+1);
		Add(b, a, i+1);
	}
	for (i = 0; i < N; i++){
		E[F[i]].push_back(i);
		if (deg[i] > 1) E[F[i + N]].push_back(i + N);
	}
	Do(P);
	if (deg[P] != 1) Do(P + N);
	for (i = 0; i < Q; i++) answer(Res[i]);
}

Compilation message (stderr)

garden.cpp: In function 'void DFS(int, int)':
garden.cpp:16:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for (i = 0; i < E[a].size(); i++){
      |              ~~^~~~~~~~~~~~~

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