제출 #375022

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
375022		LucaDantas	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	0 / 100	9 ms	12140 KiB

garden

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

constexpr int maxn = 5e5+10;

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

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

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

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
	n = N; lim = N; p = P;
	for(int i = 0; i < 3*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(f[f[a]] == a) dirty[a] = 1;
	
	for(int a = 0; a < N; a++) {
		if(!dirty[a]) continue;
		if(s[f[a]] != -1)
			f[n] = s[f[a]], f[a] = n++;
		else {
			if(s[a] == -1) continue;
			f[n] = n+1; f[n+1] = s[a];
			f[a] = n; n += 2;
		}
	}
	
	for(int i = 0; i < n; i++)
		g[f[i]].push_back(i);

	// for(int i = 0; i < n; i++)
	// 	printf("%d %d\n", i, f[i]);
	
	dfs(P, 0);
	dfs2(P);
	// printf("%d\n", sz);
	for(int i = 0; i < sz; i++)
		for(int j = i; j < n; j += sz)
			ans[i] += dist[j];
	for(int i = 0; i < Q; i++) {
		int sub = 0;
		for(int j = G[i]+sz; sz && j < n; j += sz)
			sub += dist[j];
		answer(ans[G[i]%sz] - sub);
	}
}

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