oj.uz

답안 #242161

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
242161 2020-06-27T03:38:05 Z MohamedAhmed04 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
0 / 100
 9 ms 7552 KB 
#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)
					flag = true ;
			}
			if(dist[j][1] != -1)
			{
				if(dist[j][1] == x)
					flag = true ;
				if(cycle[j] && dist[j][1] % cycle_sz == x)
					flag = true ;
			}
			ans += flag ;
		}
		answer(ans) ;
	}
}

Subtask #1
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 7552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 7552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 7552 KB Output isn't correct
2 Halted 0 ms 0 KB -