Submission #551262

#	Time	Username	Problem	Language	Result	Execution time	Memory
551262		Sohsoh84	Tropical Garden (IOI11_garden)	C++17	100 / 100	2416 ms	48872 KiB

garden

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

using namespace std;

typedef long long ll;

#define debug(x)			cerr << #x << ": " << x << endl;

const ll MAXN = 1e6 + 10;

int n, m, p, deg[MAXN], F[MAXN], dist[2][MAXN], cyc[2];
vector<int> adj[MAXN];
bool vis[MAXN];

inline void add_edge(int u, int v) {
	F[u] = v;
	adj[v].push_back(u);
}

inline void add(int u, int v) {
	if (deg[u] > 1) return;
	if (deg[u] == 0) {
		if (deg[v] == 0) add_edge(u << 1 | 1, v << 1);
		else add_edge(u << 1 | 1, v << 1 | 1);
	} else {
		if (deg[v] == 0) add_edge(u << 1, v << 1);
		else add_edge(u << 1, v << 1 | 1);
	}
}

void dfs(int v, int len, int ind) {
	vis[v] = true;
	dist[ind][v] = len;
	for (int u : adj[v]) {
		if (vis[u]) cyc[ind] = len;
		else
			dfs(u, len + 1, ind);
	}
}

inline bool f(int ind, int v, int k) {
	if (!dist[ind][v]) return false;
	k -= dist[ind][v] - 1;

	if (k == 0) return true;
	if (k < 0) return false;
	return cyc[ind] && k % cyc[ind] == 0;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
	n = N, m = M, p = P;
	p++;
	for (int i = 0; i < m; i++) {
		int u = R[i][0], v = R[i][1];
		u++;
		v++;

		add(u, v);
		add(v, u);
		deg[u]++;
		deg[v]++;
	}

	for (int v = 1; v <= n; v++)
		if (!F[v << 1])
			add_edge(v << 1, F[v << 1 | 1]);
	
	dfs(p << 1, 1, 0);
	memset(vis, false, sizeof vis);
	dfs(p << 1 | 1, 1, 1);

	for (int i = 0; i < Q; i++) {
		int ans = 0;
		for (int v = 1; v <= n; v++)
			ans += (f(0, v << 1 | 1, G[i]) || f(1, v << 1 | 1, G[i]));

		answer(ans);
	}
}

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