Submission #390141

#	Time	Username	Problem	Language	Result	Execution time	Memory
390141		AriaH	Tropical Garden (IOI11_garden)	C++11	0 / 100	21 ms	24524 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10;

int deg[N], Mn[N], F[N], D[N], n, Res[N];

bool v[N];

vector < int > E[N];
 
void DFS(int a, int d)
{
	int i;
	D[a] = d;
	for (i = 0; i < (int)E[a].size(); i++){
		if (D[E[a][i]] == -1)DFS(E[a][i], d + 1);
	}
}
 
int QQ, DD[N];

struct Query{
	int a, num;
	bool operator<(const Query &p)const{
		return a < p.a;
	}
}w[N];
 
int S[N];
 
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 N2, int M, int P, int R[][2], int Q, int G[])
{
	int i, a, b;
	n = N2;
	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 * N2; 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 + N2]].push_back(i + N2);
	}
	Do(P);
	if (deg[P] != 1)Do(P + N);
	for (i = 0; i < Q; i++)answer(Res[i]);
}

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