oj.uz

답안 #23605

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
23605 2017-05-15T21:38:27 Z Hiasat 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
0 / 100
 42 ms 40824 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

vector< pii > g[150001];

int dp[150001][2][31];
int last[150001][2][31];
int mx[150001][2][31];

pii need[150001][2];

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	for (int i = 0; i < M; ++i) {
		g[R[i][0]].push_back(make_pair(R[i][1], i));
		g[R[i][1]].push_back(make_pair(R[i][0], i));
	}
	memset(dp, -1, sizeof dp);

	for (int i = 0 ; i < N ; i++) {
		if (g[i].size()) {
			dp[i][0][0] = dp[i][1][0] = g[i][0].first;
			last[i][0][0] = last[i][1][0] = g[i][0].second;
			if (g[i][0].first == P) {
				mx[i][0][0] = 1;
			}
		}
		if (g[i].size() > 1) {
			dp[i][1][0] =  g[i][1].first;
			last[i][1][0] = g[i][1].second;
			if (g[i][1].first == P) {
				mx[i][1][0] = 1;
			}
		}
	}
	for (int k = 1 ; k <= 30; k++)
		for (int i = 0 ; i < N ; i++) {
			for (int it = 0 ; it < 2 ; it++) {
				if (dp[i][it][k - 1] != -1) {
					int vv = dp[i][it][k - 1];
					int uu = last[i][it][k - 1];
					dp[i][it][k] = dp[vv][(g[vv][0].second == uu)][k - 1];
					last[i][it][k] = last[vv][(g[vv][0].second == uu)][k - 1];
					mx[i][it][k] = max(mx[i][it][k - 1], mx[vv][(g[vv][0].second == uu)][k - 1]);
				}
			}
		}
	for (int i = 0 ; i < N ; i++) {
		for (int it = 0 ; it < 2 ; it++) {
			int go = i;
			int ll = !it?-1:g[i][0].second;
			int t = 0;
			for (int k = 30 ; k >= 0 ; k--) {
				if (mx[go][ll == g[go][0].second][k] == 0) {
					t += (1 << k);
					int nw = dp[go][ll == g[go][0].second][k];
					ll = last[go][ll == g[go][0].second][k];
					go = nw;
				}
			}
			if(dp[go][ll == g[go][0].second][0] == P){
				bool equal = last[go][ll == g[go][0].second][0] == g[P][0].second;
				need[i][it] = make_pair(t+1,equal);
			}
		}
	}
	for (int i = 0 ; i < Q ; i++) {
		int cnt = 0;
		for (int j = 0 ; j < N ; j++) {
			if(G[i] < need[j][0].first)
				continue;
			int rem = G[i] - need[j][0].first;
			int curIt = need[j][0].second;
			while(rem >= need[0][curIt].first){
				rem -= need[0][curIt].first;
				curIt = need[0][curIt].second;
			}
			if (rem == 0)
				cnt++;
		}
		answer(cnt);
	}
}

Subtask #1
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 40696 KB Output is correct
2 Correct 39 ms 40812 KB Output is correct
3 Correct 42 ms 40804 KB Output is correct
4 Correct 40 ms 40284 KB Output is correct
5 Correct 34 ms 40312 KB Output is correct
6 Incorrect 39 ms 40824 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 40696 KB Output is correct
2 Correct 39 ms 40812 KB Output is correct
3 Correct 42 ms 40804 KB Output is correct
4 Correct 40 ms 40284 KB Output is correct
5 Correct 34 ms 40312 KB Output is correct
6 Incorrect 39 ms 40824 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 40696 KB Output is correct
2 Correct 39 ms 40812 KB Output is correct
3 Correct 42 ms 40804 KB Output is correct
4 Correct 40 ms 40284 KB Output is correct
5 Correct 34 ms 40312 KB Output is correct
6 Incorrect 39 ms 40824 KB Output isn't correct
7 Halted 0 ms 0 KB -