Submission #43677

#	Time	Username	Problem	Language	Result	Execution time	Memory
43677		baactree	Tropical Garden (IOI11_garden)	C++14	100 / 100	305 ms	55616 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
int n, m, p;
vector<int> adj[150005];
vector<int> sadj[300005];
int v[300005], s[300005], cnt[300005];
int vn, sn;
stack<int> st;
int dfs(int now) {
	int ret = v[now] = vn++;
	st.push(now);
	for (auto &there : sadj[now]) {
		if (v[there] == -1)
			ret = min(ret, dfs(there));
		else if (s[there] == -1)
			ret = min(ret, v[there]);
	}
	if (ret == v[now]) {
		while (true) {
			int temp = st.top();
			st.pop();
			s[temp] = sn;
			cnt[sn]++;
			if (temp == now)break;
		}
		sn++;
	}
	return ret;
}
vector<int> dist[2][300005];
int trip[300005];
void bfs(int st, int mode) {
	int k = cnt[s[st]];
	memset(trip, -1, sizeof(trip));
	queue<int> q;
	q.push(st);
	trip[st] = 0;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		if (now % 2 == 0)dist[mode][k == 1 ? trip[now] : trip[now] % k].push_back(trip[now]);
		for (auto &there : sadj[now]) {
			if (trip[there] == -1) {
				trip[there] = trip[now] + 1;
				q.push(there);
			}
		}
	}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	n = N; m = M; p = P;
	for (int i = 0; i < m; i++) {
		adj[R[i][0]].push_back(R[i][1]);
		adj[R[i][1]].push_back(R[i][0]);
	}
	for (int now = 0; now < n; now++) {
		int there = adj[now][0];
		int u = now * 2;
		int v = there * 2 + (adj[there].size() > 1 && adj[there][0] == now);
		sadj[v].push_back(u);
		if (adj[now].size() > 1) {
			there = adj[now][1];
			int u = now * 2 + 1;
			int v = there * 2 + (adj[there].size() > 1 && adj[there][0] == now);
			sadj[v].push_back(u);
		}
	}
	memset(v, -1, sizeof(v));
	memset(s, -1, sizeof(s));
	for (int i = 0; i < n * 2; i++)
		if (v[i] == -1)dfs(i);
	for (int i = 0; i < 2; i++) 
		bfs(p * 2 + i, i);
	for (int i = 0; i < Q; i++) {
		int ans = 0;
		for (int j = 0; j < 2; j++) {
			int st = p * 2 + j;
			int k = cnt[s[st]];
			if (k == 1) {
				if(G[i]<300005)
					ans += dist[j][G[i]].size();
			}
			else {
				ans += upper_bound(dist[j][G[i] % k].begin(), dist[j][G[i] % k].end(), G[i]) - dist[j][G[i] % k].begin();
			}
		}
		answer(ans);
	}
}

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