oj.uz

답안 #39297

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
39297 2018-01-11T03:17:16 Z 14kg 열대 식물원 (Tropical Garden) (IOI11_garden) C++11
0 / 100
 2 ms 376 KB 
#include "garden.h"
#include "gardenlib.h"
#include <algorithm>
#include <vector>
#define N 150001
#define MP 23

using namespace std;
int n, m, start, cycle1_len, cycle2_len;
int Sx, Sy, d[N][2], d1[N][2], d2[N][2];
pair<int, int> r[N];

void Push_r(int x, int y) {
	if (!r[x].first) r[x].first = y;
	else if (!r[x].second) r[x].second = y;
}
int dfs(int x, int y, int len) {
	d[x][y] = len;
	int nx = y ? r[x].second : r[x].first;
	int ny = r[nx].second && r[nx].first == x ? 1 : 0;

	if (d[nx][ny]) {
		if (d[nx][ny] == 1) return len;
		else return -1;
	}
	return dfs(nx, ny, len + 1);
}
int dfs_find1(int x, int y) {
	if (x == start && y == 0) return 0;
	if (d1[x][y] != 0) return d1[x][y];

	int nx = y ? r[x].second : r[x].first;
	int ny = r[nx].second && r[nx].first == x ? 1 : 0;

	d1[x][y] = -1, d1[x][y] = dfs_find1(nx, ny);
	if (d1[x][y] >= 0) d1[x][y]++;

	return d1[x][y];
}
int dfs_find2(int x, int y) {
	if (x == start && y == 1) return 0;
	if (d2[x][y] != 0) return d2[x][y];

	int nx = y ? r[x].second : r[x].first;
	int ny = r[nx].second && r[nx].first == x ? 1 : 0;

	d2[x][y] = -1, d2[x][y] = dfs_find2(nx, ny);
	if (d2[x][y] >= 0) d2[x][y]++;

	return d2[x][y];
}
void count_routes(int _n, int _m, int _s, int _r[][2], int Q_len, int Q[]) {
	n = _n, start = _s + 1;
	for (int i = 0; i < _m; i++) {
		int x = _r[i][0] + 1, y = _r[i][1] + 1;
		Push_r(x, y), Push_r(y, x);
	}

	cycle1_len = dfs(start, 0, 1);
	for (int i = 1; i <= n; i++) d[i][0] = d[i][1] = 0;
	cycle2_len = dfs(start, 1, 1);
	for (int i = 1; i <= n; i++) d[i][0] = d[i][1] = 0;
	
	for (int i = 1; i <= n; i++) {
		if (d1[i][0] == 0) dfs_find1(i, 0);
		if (d2[i][0] == 0) dfs_find2(i, 0);
	}

	for (int i = 0; i < Q_len; i++) {
		int res = 0;
		if (Q[i] == 0) { answer(1); continue; }
		for (int j = 1; j <= n; j++) {
			if (d1[j][0] == Q[i] || d2[j][0] == Q[i]) res++;
			else if ((d1[j][0] > 0 || j == start) && cycle1_len > 0 && Q[i] > d1[j][0] && (Q[i] - d1[j][0]) % cycle1_len == 0) res++;
			else if ((d2[j][0] > 0 || j == start) && cycle2_len > 0 && Q[i] > d1[j][0] && (Q[i] - d2[j][0]) % cycle2_len == 0) res++;
		} answer(res);
	}
}

Subtask #1
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -