제출 #367904

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

garden

#include <bits/stdc++.h>
using namespace std;
#define sz(a) ((int)(a).size())
typedef vector<int> vint;
typedef vector<vint> vvint;
#ifndef wambule
#include "garden.h"
#include "gardenlib.h"
#else
void answer(int x) {
	cout << "[!] " << x << endl;
}
#endif

namespace blob {
	int p, pp;
}

void G(int x, int x2[], int x4[], int x5[], int x6[], int x7[], int x8[], int x9[], int &z) {
	x7[x] = z;
	++z;
	int y = x6[x];
	if(x7[y]) {
		if(x5[y]) {
			x2[x] = -1;
			if(x != blob::p) x4[x] = (x4[y] == -1 ? -1 : x4[y] + 1);
			if(x != blob::pp) x9[x] = (x9[y] == -1 ? -1 : x9[y] + 1);
			x5[x] = 1;
		} else {
			if(x7[blob::p] >= x7[y]) {
				if(x != blob::p) x4[x] = x7[blob::p] - x7[y] + 1;
			}
			if(x7[blob::pp] >= x7[y]) {
				if(x != blob::pp) x9[x] = x7[blob::pp] - x7[y] + 1;
			}
			x2[x] = x7[x] - x7[y] + 1;
			x8[y] = 1;
		}
		x5[x] = 1;
		return;
	}
	G(y, x2, x4, x5, x6, x7, x8, x9, z);
	x2[x] = (x8[y] ? -1 : x2[y]);
	if(x != blob::p) x4[x] = (x4[y] == -1 ? -1 : x4[y] + 1);
	if(x != blob::pp) x9[x] = (x9[y] == -1 ? -1 : x9[y] + 1);
	x5[x] = 1;
}

void count_routes(int n, int m, int p, int r[][2], int q, int gg[]) {
	blob::p = p;
	int pp = p + n;
	blob::pp = pp;
	int N = 2 * n;
	int x2[N], x4[N], x5[N];
	int x6[N], x7[N], x8[N], x9[N];
	vint v[n];
	for(int i = 0; i < N; ++i) {
		x5[i] = x7[i] = x8[i] = 0;
		x4[i] = (i == p ? 0 : -1);
		x9[i] = (i == pp ? 0 : -1);
		x2[i] = -1;
	}
	for(int i = 0; i < m; ++i) {
		if(sz(v[r[i][0]]) < 2) v[r[i][0]].push_back(r[i][1]);
		if(sz(v[r[i][1]]) < 2) v[r[i][1]].push_back(r[i][0]);
	}
	for(int i = 0; i < n; ++i) {
		x6[i] = v[i][0];
		x6[i + n] = v[i][(sz(v[i]) == 2)];
	}
	for(int i = 0; i < N; ++i) {
		if(x6[x6[i]] == i || x6[x6[i]] == (i >= n ? i - n : i + n)) {
			x6[i] += n;
		}
	}
	#ifdef wambule
	for(int i = 0; i < N; ++i) {
		// cout << (i >= n ? i - n : i) << ", " << (i >= n) << " -> " << x6[i] << endl;
		cout << i << " " << x6[i] << endl;
	}
	#endif
	int z = 1;
	for(int i = 0; i < N; ++i) {
		int x = i;
		if(!x5[x]) {
			G(x, x2, x4, x5, x6, x7, x8, x9, z);
		}
	}
	for(int qi = 0; qi < q; ++qi) {
		int g = gg[qi];
		int ap = 0;
		for(int i = 0; i < n; ++i) {
			if(x4[i] != -1) {
				if(x2[p] == -1) {
					if(x4[i] == g) {
						++ap;
						continue;
					}
				} else {
					if(g >= x4[i]) {
						if((g - x4[i]) % x2[p] == 0) {
							++ap;
							continue;
						}
					}
				}
			}
			if(x9[i] != -1) {
				if(x2[pp] == -1) {
					if(x9[i] == g) {
						++ap;
						continue;
					}
				} else {
					if(g >= x9[i]) {
						if((g - x9[i]) % x2[pp] == 0) {
							++ap;
							continue;
						}
					}
				}
			}
			// cout << "[ O ] " << i << endl;
		}
		answer(ap);
	}
	#ifdef wambule
	for(int i = 0; i < N; ++i) {
		cout << i << " - " << x2[i] << " " << x4[i] << " " << x9[i] << endl;
	}
	#endif
}

#ifdef wambule
#define C

#ifdef A
int n = 6;
int m = 6;
int p = 0;
int q = 2;
int g[] = {3, 102};
int r[][2] = {1, 2, 0, 1, 0, 3, 3, 4, 4, 5, 1, 5};
#endif
#ifdef B
int n = 5;
int m = 5;
int p = 2;
int q = 2;
int g[] = {3, 1};
int r[][2] = {1, 0, 1, 2, 3, 2, 1, 3, 4, 2};
#endif
#ifdef C
int n = 5;
int m = 5;
int p = 0;
int q = 2;
int g[] = {3, 5};
int r[][2] = {0, 1, 1, 2, 2, 3, 3, 4, 4, 0};
#endif

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	count_routes(n, m, p, r, q, g);
	return 0;
}
#endif

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