Submission #13480

#	Time	Username	Problem	Language	Result	Execution time	Memory
13480		ainta	Tropical Garden (IOI11_garden)	C++98	100 / 100	142 ms	27900 KiB

garden

#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:15:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < E[a].size(); i++){
              ~~^~~~~~~~~~~~~

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