Submission #1087238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087238		dubabuba	Tropical Garden (IOI11_garden)	C++14	0 / 100	5 ms	13400 KiB

garden

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

using namespace std;

const int mxn = 1.5e5 + 1000;
const int MXN = 3e5 + 100000;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

vector<int> adj[mxn]; // OG graph
vector<int> rev[MXN]; // buba graph
int dis[MXN], fdis[MXN], nxt[MXN];
bool vis[MXN];

bool fake(int cur, int prv) {
	if(adj[cur].size() == 1) return 0;
	return prv == adj[cur][0];
}

void build_buba(int cur, int prv = -1) {
	int bu = cur + mxn * fake(cur, prv);

	if(vis[bu]) return;
	vis[bu] = 1;
	
	int sus = 0;
	if(adj[cur].size() == 1) sus = adj[cur][0];
	else if(prv == adj[cur][0]) sus = adj[cur][1];
	else sus = adj[cur][0];

	int bv = sus + mxn * fake(sus, cur);
	nxt[bu] = bv;
	rev[bv].push_back(bu);

	build_buba(sus, cur);
}

void bfs(int P, int dis[]) {
	priority_queue<pii> pq;
	pq.push(MP(0, P));
	for(int i = 0; i < MXN; i++)
		dis[i] = -1;

	while(pq.size()) {
		int d = -pq.top().ff;
		int u = pq.top().ss;
		pq.pop();

		if(dis[u] > -1) continue;
		dis[u] = d;

		for(int v : rev[u])
			if(dis[v] == -1)
				pq.push(MP(-d-1, v));
	}
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
	answer(2);
	return;
	for(int i = 0; i < M; i++) {
		int u = R[i][0];
		int v = R[i][1];
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	memset(nxt, -1, sizeof nxt);
	for(int i = 0; i < N; i++)
		build_buba(i, -1);
	memset(vis, 0, sizeof vis);
	
	vector<int> path, cyc;
	int node = 0;
	while(!vis[node]) {
		vis[node] = 1;
		path.push_back(node);
		node = nxt[node];
	}

	while(path.back() != node) {
		int u = path.back();
		cyc.push_back(u);
		path.pop_back();
	}
	cyc.push_back(node);

	bool in1 = false;
	bool in2 = false;
	for(int u : cyc) {
		if(u == P) in1 = true;
		if(u == P + mxn) in2 = true;
	}

	bfs(P, dis);
	bfs(P + mxn, fdis);

	auto sus1 = [&] (int u, int D) -> bool {
		if(dis[u] == -1) return 0;
		if(dis[u] == D) return 1;
		if(dis[u] > D) return 0;
		return in1 && ((D - dis[u]) % cyc.size() == 0);
	};

	auto sus2 = [&] (int u, int D) -> bool {
		if(fdis[u] == -1) return 0;
		if(fdis[u] == D) return 1;
		if(fdis[u] > D) return 0;
		return in2 && ((D - fdis[u]) % cyc.size() == 0);
	};

	for(int i = 0; i < Q; i++) {
		int D = G[i] - 1, ans = 0;
		for(int u = 0; u < N; u++) {
			if(sus1(u, D) || sus2(u, D))
				ans++;
		}
		answer(ans);
	}
}

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