Submission #416078

#	Time	Username	Problem	Language	Result	Execution time	Memory
416078		dreezy	Tropical Garden (IOI11_garden)	C++17	0 / 100	1129 ms	262148 KiB

garden

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


/*****************************************/

//just have to implement
#define pi pair<int,int>
#define pb push_back
#define ll long long
#define f first
#define s second

const int maxn = 1e3 +5;
//int level[maxn];
set<pi> graph[maxn];

ll bfs(int n, int k){
	queue<tuple<int,int,int>> bfsq;//curnode, parent, level
	
	//for(pi adj : graph[n]){
		//bfsq.push({adj.f, n, 1 });
	//}
	bfsq.push({n,-1, 0});
	
	ll ans = 0;
	//cout << k <<":\n\n";
	
	while(bfsq.size()){
		int node, parent, level;
		
		tie(node, parent,level) = bfsq.front();
		bfsq.pop();
		
		if(level > k) continue;
		
		if(graph[node].begin()->s != parent && parent != -1 ){
			if(graph[node].size()>1 && next(graph[node].begin())->s == parent )
				bfsq.push({next(graph[node].begin())->s, node, level + 1});
			continue;
		}
		
		//cout << node <<", "<<parent<<", "<<level<<"\n";
		if(level == k)
		{	
			//cout <<"YES\n";
			ans++;
			continue;
		}
		
		
		
	//	if(graph[node].size() == 1){
		//	bfsq.push({graph[node].begin()->s, node, level +1});
			//continue;
		//}
		
		for(pi adj : graph[node]){
			
			auto fadj = graph[adj.s].begin();
			if(fadj->s == node){
				bfsq.push({adj.s, node, level +1});
				//cout << level<<": "<<node <<"->"<<adj.s<<'\n';
			}
			
			else if(graph[adj.s].size() > 1 && next(fadj)->s == node){
				bfsq.push({fadj->s, adj.s, level + 2 });
				//cout << level<<"+: "<<node <<"->"<<adj.s<<"->"<<fadj->s<<'\n';
			}
		}
		
	}
	return ans;
	
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
		
  for(int i =0; i<M; i++){
	  graph[R[i][0]].insert({i,R[i][1] });
	  graph[R[i][1]].insert({i,R[i][0]});
  }

	
  for(int i =0; i<Q; i++){
	ll res = bfs(P, G[i]);
	answer(res);  
  }

   
}

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