Submission #375492

#	Time	Username	Problem	Language	Result	Execution time	Memory
375492		LucaDantas	Tropical Garden (IOI11_garden)	C++17	100 / 100	151 ms	35308 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include<vector>
#include<cstdio>
#include<cstring>

constexpr int maxn = 3e5+10;

std::vector<int> g[maxn]; // functional graph reversed
int f[maxn], s[maxn], dist[maxn][2], ans[maxn][2], n, lim, sz[2];
bool mark[maxn];

void dfs(int u, int d, int k) {
	mark[u] = 1;
	if(u < lim) ++dist[d][k];
	for(int v : g[u])
		if(!mark[v]) dfs(v, d+1, k);
}

void dfs2(int u, int k, int p) {
	mark[u] = 1; ++sz[k];
	if(f[u] == p) return;
	if(mark[f[u]]) return (void)(sz[k] = maxn);
	dfs2(f[u], k, p);
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
	n = 2*N; lim = N;
	for(int i = 0; i < n; i++)
		f[i] = s[i] = -1;
	for(int i = 0; i < M; i++) {
		int a = R[i][0], b = R[i][1];
		
		if(f[a] == -1) f[a] = b;
		else if(s[a] == -1) s[a] = b;

		if(f[b] == -1) f[b] = a;
		else if(s[b] == -1) s[b] = a;
	}
	
	for(int a = 0; a < N; a++) {
		if(s[a] == -1) s[a] = f[a];
		if(f[f[a]] == a) g[f[a]+N].push_back(a);
		else g[f[a]].push_back(a);
		if(f[s[a]] == a) g[s[a]+N].push_back(a+N);
		else g[s[a]].push_back(a+N);
	}

	for(int i = 0; i < n; i++) {
		for(int v : g[i])  {
			f[v] = i;
		}
	}
	
	dfs(P, 0, 0);
	memset(mark, 0, sizeof mark);
	dfs(P+N, 0, 1);
	memset(mark, 0, sizeof mark);

	dfs2(P, 0, P);
	memset(mark, 0, sizeof mark);
	dfs2(P+N, 1, P+N);
	memset(mark, 0, sizeof mark);

	int last[maxn][2]{};
	for(int b = 0; b <= 1; b++) {
		for(int i = 0; i < n; i++) {
			ans[i][b] = (i>=sz[b]?ans[i-sz[b]][b]:0) + dist[i][b];
			last[i%sz[b]][b] = i;
		}
	}
	for(int i = 0; i < Q; i++) {
		int here = 0;
		for(int b = 0; b <= 1; b++) {
			if(sz[b] < maxn) {
				here += ans[std::min(G[i], last[G[i]%sz[b]][b])][b];
			} else {
				if(G[i] < n) here += dist[G[i]][b];
			}
		}
		answer(here);
	}
}

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