제출 #753712

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

garden

/**
 *      Author:  Nicholas Winschel
 *      Created: 05.10.2023 22:07:36
**/

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())

void answer(int X);
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]);

int inf = 1e9+500;

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
	V<vi> r(2*N);
	vi f(2*N, -1);
	for (int i = 0; i < M; i++) {
		if (f[R[i][0]] == -1 && f[R[i][1]] == -1) {
			f[R[i][0]] = R[i][1]+N;
			f[R[i][1]] = R[i][0]+N;
		} else if (f[R[i][0]] == -1) {
			f[R[i][0]] = R[i][1];
			if (f[R[i][1]+N]==-1) {
				f[R[i][1]+N]=R[i][0]+N;
			}
		} else if (f[R[i][1]] == -1) {
			f[R[i][1]] = R[i][0];
			if (f[R[i][0]+N]==-1) {
				f[R[i][0]+N]=R[i][1]+N;
			}

		} else if (f[R[i][0]+N] == -1 || f[R[i][1]+N]==-1) {
			if (f[R[i][0]+N]==-1) f[R[i][0]+N]=R[i][1];
			if (f[R[i][1]+N]==-1) f[R[i][1]+N]=R[i][0];
		} 
	}
	for (int i = 0; i < N; i++) {
		if (f[i+N]==-1) f[i+N]=f[i];
		r[f[i]].push_back(i);
		r[f[i+N]].push_back(i+N);
	}
	vi ub(2*N, inf), b(2*N,inf);
	V<bool> vis(2*N);
	auto dfs = [&](int v, int c, auto &&dfs) -> int {
		if (vis[v]) return c;
		vis[v]=true;
		ub[v]=c;
		int ret = 0;
		for (int x : r[v]) {
			ret = max(ret, dfs(x,c+1,dfs));
		}
		return ret;
	};
	int cub = dfs(P,0,dfs);
	swap(ub,b);
	vis=V<bool>(2*N);
	int cb = dfs(P+N,0,dfs);
	swap(ub,b);
	for (int i = 0; i < Q; i++) {
		int K = G[i];
		int ans = 0;
		for (int i = 0; i < N; i++) {
			if ((ub[i] <= K && (ub[i] == K || (cub && (K-ub[i])%cub == 0)))
				|| (b[i] <= K && (b[i] == K || (cb && (K-b[i])%cb == 0)))) ans++;
		}
		answer(ans);
	}
}

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