Submission #248975

#	Time	Username	Problem	Language	Result	Execution time	Memory
248975		eohomegrownapps	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	100 / 100	2780 ms	24588 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
//answer(N) -- query

int n;
int INF = 1e9;
int p;
vector<vector<int>> adjlist;

vector<vector<pair<int,int>>> dp; 
//node, comes from beautiful
//until k, type of k visit
//-1 - never cycles, 0 - returns unblocked, 1 - returns blocked

pair<int,int> genk(int node, bool blocked, bool start){
	//cout<<node<<" "<<blocked<<'\n';
	if (node==p&&!start){
		//we've found p
		return {0,blocked};
	}
	if (dp[node][blocked].first!=-1){
		return dp[node][blocked];
	}
	if (dp[node][blocked].second==true){
		//we've reached a cycle
		return dp[node][blocked]={INF,-1};
	}
	dp[node][blocked].second = true; //to check for cycles
	int next = adjlist[node][0];
	if (adjlist[node].size()>1&&blocked){
		next = adjlist[node][1];
	}
	bool isBlocked = adjlist[next][0]==node;
	pair<int,int> ans = genk(next,isBlocked,false);
	if (ans.first==INF){
		return dp[node][blocked]={INF,-1};
	} else {
		return dp[node][blocked]={ans.first+1,ans.second};
	}
}

pair<int,int> followpath(int node, bool blocked){
	if (node==p){
		return {0,blocked};
	}
	if (dp[node][blocked].first!=-1){
		return dp[node][blocked];
	}
	if (dp[node][blocked].second==true){
		//we've reached a bad cycle
		return dp[node][blocked]={INF,false};
	}
	dp[node][blocked].second = true; //to check for cycles
	int next = adjlist[node][0];
	if (adjlist[node].size()>1&&blocked){
		next = adjlist[node][1];
	}
	bool isBlocked = adjlist[next][0]==node;
	pair<int,int> ans = followpath(next,isBlocked);
	if (ans.first==INF){
		return dp[node][blocked]={INF,false};
	} else {
		return dp[node][blocked]={ans.first+1,ans.second};
	}
}

bool routeExists(int i, int val){
	if (dp[i][0].first>=INF){
		return false;
	}
	if (dp[i][0].first>val){
		return false;
	}
	/*if (dp[i][0].first==val){
		return true;
	}*/
	bool b = dp[i][0].second;
	if (dp[p][b].first>=INF){
		//X->?
		return val==dp[i][0].first;
	} else if (dp[p][b].second==b){
		//X->X
		val-=dp[i][0].first;
		return val%dp[p][b].first==0;
	} else {
		val-=dp[i][0].first;
		//X->Y
		if (val==0){return true;}
		if (dp[p][!b].first>=INF){
			//X->Y->?
			return val==dp[p][b].first;
		} else if (dp[p][!b].second==!b){
			//X->Y->Y
			val-=dp[p][b].first;
			return val%dp[p][!b].first==0;
		} else {
			//X->Y->X
			val%=(dp[p][b].first+dp[p][!b].first);
			return (val==0||val==dp[p][b].first);
		}
	}
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
	n=N;p=P;
	adjlist.resize(n);
	dp.resize(n,vector<pair<int,int>>(2,{-1,false}));
	for (int i = 0; i<M; i++){
		adjlist[R[i][0]].push_back(R[i][1]);
		adjlist[R[i][1]].push_back(R[i][0]);
	}
	//cout<<"gen\n";
	genk(p,false,true);
	//cout<<dp[p][0].first<<'\n';
	//cout<<"gen\n";
	genk(p,true,true);
	//cout<<dp[p][1].first<<'\n';
	for (int i = 0; i<n; i++){
		for (int blocked = 0; blocked<2; blocked++){
			if (dp[i][blocked].first==-1){
				followpath(i,blocked);
			}
		}
	}

	//todo: check for case where inf
	for (int q = 0; q<Q; q++){
		int cnt = 0;
		int val = G[q];
		for (int i = 0; i<n; i++){
			if (routeExists(i,val)){
				cnt++;
			}
		}
		answer(cnt);
	}
}

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