Submission #216959

#	Time	Username	Problem	Language	Result	Execution time	Memory
216959		Kenzo_1114	Tropical Garden (IOI11_garden)	C++17	0 / 100	9 ms	7552 KiB

garden

#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
const int INF = 1e9 + 7;
const int MAXN = 300010;
const int MAXQ = 2010;

int N, M, P, R[MAXN][2], Q, G[MAXQ];

int n, idCycle[MAXN], idInCycle[MAXN], parCycle[MAXN], adj[MAXN], depth[MAXN], quantity[MAXN];
int in[MAXN], mark[MAXN], dist[MAXN], comp;
bool inCycle[MAXN], outCycle[MAXN];

queue<int> q;
vector<int> v, graph[MAXN];

void functional_graph()
{
	for(int i = 0; i < 2 * n; i++)
		if(!in[i])	q.push(i);

	while(!q.empty())
	{
		int cur = q.front(); q.pop();
		int nex = adj[cur];

		v.push_back(cur);
		outCycle[cur] = true;
		idInCycle[cur] = -1;
		
		in[nex]--;
		if(!in[nex])	q.push(nex);
	}	

	for(int i = 0; i < 2 * n; i++)
	{
		if(outCycle[i] || inCycle[i])	continue;

		inCycle[i] = true;
		parCycle[i] = i;
		idCycle[i] = ++comp;
		idInCycle[i] = 0;

		int cur = adj[i], id = 1;
		while(cur != i)
		{
			inCycle[cur] = true;
			parCycle[cur] = cur;
			idCycle[cur] = comp;
			idInCycle[cur] = id++;
			cur = adj[cur];
		}
		quantity[comp] = id;
	}

	for(int i = v.size() - 1; i >= 0; i--)
	{
		int cur = v[i];
		parCycle[cur] = parCycle[adj[cur]];
		depth[cur] = depth[adj[cur]] + 1;
		idCycle[cur] = idCycle[adj[cur]];
	}
}

void count_routes(int n1, int m, int p, int r[][2], int queries, int g[])
{
	n = n1;

	for(int i = 0; i < 2 * n; i++)	adj[i] = -1;

	for(int i = 0; i < m; i++)
	{
		int u = r[i][0];
		int v = r[i][1];

		if(!mark[u] && !mark[v])
		{
			adj[2 * u] = 2 * v + 1;
			adj[2 * v] = 2 * u + 1;
			mark[u] = 1, mark[v] = 1;
		}
		else if(mark[u] + mark[v] == 1)
		{
			if(mark[v] == 1)	swap(u, v);
			adj[2 * u + 1] = 2 * v + 1;
			adj[2 * v] = 2 * u;
			mark[u] = 2, mark[v] = 1;
		}
		else if(mark[u] == 1 && mark[v] == 1)
		{
			adj[2 * u + 1] = 2 * v;
			adj[2 * v + 1] = 2 * u;
			mark[u] = mark[v] = 2;
		}
		else if(mark[u] == 2 && mark[v] == 2)	continue;
		else if(mark[u] == 2 || mark[v] == 2)
		{
			if(mark[v] == 2)	swap(u, v);
			if(mark[v] == 0)	adj[2 * v] = 2 * u, 	mark[v] = 1;
			if(mark[v] == 1)	adj[2 * v + 1] = 2 * u, mark[v] = 2;
		}
	}

	for(int i = 0; i < n; i++)
		if(adj[2 * i + 1] == -1)
			adj[2 * i + 1] = adj[2 * i];

	for(int i = 0; i < 2 * n; i++)
	{
//		printf("%d -> %d\n", i, adj[i]);
		in[adj[i]]++;
	}

	functional_graph();//see();

	p *= 2;
	int idP  = (inCycle[p]) ? idInCycle[p] : -1;
	int idP2 = (inCycle[p + 1]) ? idInCycle[p + 1] : -1;

	for(int i = 0; i < queries; i++)
	{
		int ans = 0;

		for(int j = 0; j < n; j++)
		{
			int u = 2 * j;

			if(idCycle[u] == idCycle[p])
			{
				if(idP != -1)
				{
					int dist = depth[u];
					u = parCycle[u];
					if((idInCycle[u] + g[i] - dist) % quantity[idCycle[p]] == idP)	ans++;//printf("C1 %d\n", u);
				}
				else
					if(parCycle[u] == parCycle[p] && depth[u] - depth[p] == g[i])	ans++;// printf("C3 %d\n", u);
			}

			if(idCycle[u] == idCycle[p + 1])
			{
				if(idP2 != -1)
				{
					int dist = depth[u];
					u = parCycle[u];
					if((idInCycle[u] + g[i] - dist) % quantity[idCycle[p + 1]] == idP2)	ans++;// printf("C2 %d\n", u);
				}
				else
					if(parCycle[u] == parCycle[p + 1] && depth[u] - depth[p + 1] == g[i])ans++;// printf("C4 %d\n", u);
			}
		}

		answer(ans);
//		printf("%d ", ans);
	}
//	printf("\n");
}

/*
int main ()
{
	scanf("%d %d %d", &N, &M, &P);

	for(int i = 0; i < M; i++)	
		scanf("%d %d", &R[i][0], &R[i][1]);

	scanf("%d", &Q);

	for(int i = 0; i < Q; i++)	scanf("%d", &G[i]);

	count_routes(N, M, P, R, Q, G);
}
*/

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