Submission #242162

#	Time	Username	Problem	Language	Result	Execution time	Memory
242162		MohamedAhmed04	Tropical Garden (IOI11_garden)	C++14	0 / 100	9 ms	7552 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
//#include "grader.cpp" 

using namespace std ;

const int MAX = 2 * 150010 ; 

int vis[MAX] , to[MAX] , best[MAX] , best2[MAX] , dist[MAX][2] , cycle[MAX] , edge[MAX][2] ;

vector< vector<int> >rev_adj(MAX) ;

int n , m ;

void Addedge(int x , int y , int val)
{
	if(best[x] == val)
	{
		if(best[y] == val)
			to[x] = y+n ;
		else
			to[x] = y ;
	}
	else if(best2[x] == val)
	{
		if(best[y] == val)
			to[x+n] = y+n ;
		else
			to[x+n] = y ;	
	}		
}

void ConstructGraph()
{
	for(int i = 0 ; i < m ; ++i)
	{
		int x = edge[i][0] ;
		int y = edge[i][1] ;
		int val = i+1 ;
		++x , ++y ;
		if(!best[x])
			best[x] = val ;
		else if(!best2[x])
			best2[x] = val ;
		if(!best[y])
			best[y] = val ;
		else if(!best2[y])
			best2[y] = val ;
		Addedge(x , y , val) ;
		Addedge(y , x , val) ;	
	}
}

void bfs(int src , bool t)
{
	for(int i = 1 ; i <= n+n ; ++i)
		dist[i][t] = -1 ;
	dist[src][t] = 0 ;
	queue<int>q ;
	q.push(src) ;
	while(!q.empty())
	{
		int node = q.front() ;
		q.pop() ;
		for(auto &child : rev_adj[node])
		{
			if(dist[child][t] == -1)
			{
				dist[child][t] = dist[node][t] + 1 ;
				q.push(child) ;
			}
		}
	}
}

int cycle_sz = 0 ;

void find_cycle()
{
	int node = 1 ;
	while(!vis[node])
	{
		vis[node] = 1 ;
		node = to[node] ;
	}
	while(vis[node] != 2)
	{
		cycle_sz++ ;
		vis[node] = 2 ;
		cycle[node] = 1 ;
		node = to[node] ;
	}
} 

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	for(int i = 0 ; i < M ; ++i)
		edge[i][0] = R[i][0] , edge[i][1] = R[i][1] ;
	P++ ;
	n = N , m = M ;
	ConstructGraph() ;
	for(int i = 1 ; i <= n+n ; ++i)
	{
		if(to[to[i]] == 0 && to[i] > 0)
			to[i] = to[i] - n ;
	}
	for(int i = 1 ; i <= n+n ; ++i)
		rev_adj[to[i]].push_back(i) ;
	bfs(P , 0) ;
	bfs(P+n , 1) ;
	find_cycle() ;
	for(int i = 0 ; i < Q ; ++i)
	{
		int x = G[i] ;
		int ans = 0 ;
		for(int j = 1 ; j <= n ; ++j)
		{
			bool flag = false ;
			if(dist[j][0] != -1)
			{
				if(dist[j][0] == x)
					flag = true ;
				if(cycle[j] && dist[j][0] % cycle_sz == x % cycle_sz)
					flag = true ;
			}
			if(dist[j][1] != -1)
			{
				if(dist[j][1] == x)
					flag = true ;
				if(cycle[j] && dist[j][1] % cycle_sz == x % cycle_sz)
					flag = true ;
			}
			ans += flag ;
		}
		answer(ans) ;
	}
}

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