oj.uz

답안 #39239

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
39239 2018-01-10T11:46:33 Z 14kg 열대 식물원 (Tropical Garden) (IOI11_garden) C++11
49 / 100
 487 ms 262148 KB 
#include "garden.h"
#include "gardenlib.h"
#include <algorithm>
#include <vector>
#define N 150001

using namespace std;
int n, m, start, p[30], R, Rw ,tot;
bool check[N][2][30];
pair<int, int> r[N];
vector<int> r1[N], r2[N];
vector<pair<int, int> > d[N][2][30];

void Push_r(int x, int y) {
	if (!r[x].first) r[x].first = y;
	else if (!r[x].second) r[x].second = y;
}
void f(int x, int y, int s) {
	if (s == 0 || check[x][y][s]) return;

	f(x, y, s - 1), check[x][y][s] = true;
	for (auto i : d[x][y][s - 1]) {
		f(i.first, i.second, s - 1);
		for (auto j : d[i.first][i.second][s - 1])
			d[x][y][s].push_back(j);
	}
}
void g(int x, int y, int R, int Rw) {
	if (R == 0) { 
		if(y==0 || r[x].first==0) tot++;
		return;
	}
	while (p[Rw] > R) Rw--;

	f(x, y, Rw);
	for (auto i : d[x][y][Rw]) g(i.first, i.second, R - p[Rw], Rw);
}
void count_routes(int _n, int _m, int _s, int _r[][2], int Q_len, int Q[]) {
	n = _n, start = _s + 1, p[0] = 1;
	for (int i = 1; i < 30; i++) p[i] = p[i - 1] * 2;

	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);
	}
	for (int i = 1; i <= n; i++) {
		if (!r[i].second) r[i].second = r[i].first, r[i].first = 0;

		if (r[i].first) r1[r[i].first].push_back(i);
		r2[r[i].second].push_back(i);
		
		if (r[r[i].first].first == i || (r[r[i].first].first == 0 && r[r[i].first].second == i)) d[r[i].first][1][0].push_back({ i,0 });
		if (r[r[i].second].first == i || (r[r[i].second].first == 0 && r[r[i].second].second == i)) d[r[i].second][1][0].push_back({ i,1 });
	}

	for (int i = 1; i <= n; i++) {
		for (auto j : r1[i])
			if (j != r[i].first && (r[i].first || r[i].second!=j)) d[i][0][0].push_back({ j,0 });
		for (auto j : r2[i])
			if (j != r[i].first && (r[i].first || r[i].second!=j)) d[i][0][0].push_back({ j,1 });
	}

	for (int i = 0; i < Q_len; i++) {
		tot = 0, g(start, 0, Q[i], 29), g(start, 1, Q[i], 29);
		answer(tot);
	}
}

Subtask #1
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 201 ms 218776 KB Output is correct
2 Correct 204 ms 218896 KB Output is correct
3 Correct 203 ms 218996 KB Output is correct
4 Correct 202 ms 218788 KB Output is correct
5 Correct 205 ms 218668 KB Output is correct
6 Correct 204 ms 218968 KB Output is correct
7 Correct 203 ms 218800 KB Output is correct
8 Correct 204 ms 218852 KB Output is correct
9 Correct 206 ms 219168 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 201 ms 218776 KB Output is correct
2 Correct 204 ms 218896 KB Output is correct
3 Correct 203 ms 218996 KB Output is correct
4 Correct 202 ms 218788 KB Output is correct
5 Correct 205 ms 218668 KB Output is correct
6 Correct 204 ms 218968 KB Output is correct
7 Correct 203 ms 218800 KB Output is correct
8 Correct 204 ms 218852 KB Output is correct
9 Correct 206 ms 219168 KB Output is correct
10 Correct 198 ms 218748 KB Output is correct
11 Correct 222 ms 222364 KB Output is correct
12 Correct 245 ms 224528 KB Output is correct
13 Runtime error 487 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 201 ms 218776 KB Output is correct
2 Correct 204 ms 218896 KB Output is correct
3 Correct 203 ms 218996 KB Output is correct
4 Correct 202 ms 218788 KB Output is correct
5 Correct 205 ms 218668 KB Output is correct
6 Correct 204 ms 218968 KB Output is correct
7 Correct 203 ms 218800 KB Output is correct
8 Correct 204 ms 218852 KB Output is correct
9 Correct 206 ms 219168 KB Output is correct
10 Correct 198 ms 218748 KB Output is correct
11 Correct 222 ms 222364 KB Output is correct
12 Correct 245 ms 224528 KB Output is correct
13 Runtime error 487 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -