oj.uz

답안 #23611

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
23611 2017-05-15T21:52:38 Z Hiasat 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
49 / 100
 645 ms 87348 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);
	memset(need,-1,sizeof need);
	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(need[j][0].first == -1)
				continue;
			if(G[i] < need[j][0].first)
				continue;
			int rem = G[i] - need[j][0].first;
	
			int curIt = need[j][0].second;
			for(int it = 0 ; it < 2 ; it++){
				if(need[P][curIt].first == -1)
					break;
				if(rem >= need[P][curIt].first){
					rem -= need[P][curIt].first;
					curIt = need[P][curIt].second;
				}
			}
			if (rem%need[P][curIt].first == 0){
				cnt++;
			}
		}
		answer(cnt);
	}
}

Subtask #1
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 43000 KB Output is correct
2 Correct 41 ms 43176 KB Output is correct
3 Correct 39 ms 43152 KB Output is correct
4 Correct 39 ms 42616 KB Output is correct
5 Correct 39 ms 42580 KB Output is correct
6 Correct 41 ms 43228 KB Output is correct
7 Correct 38 ms 42704 KB Output is correct
8 Correct 40 ms 43100 KB Output is correct
9 Correct 41 ms 43384 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 43000 KB Output is correct
2 Correct 41 ms 43176 KB Output is correct
3 Correct 39 ms 43152 KB Output is correct
4 Correct 39 ms 42616 KB Output is correct
5 Correct 39 ms 42580 KB Output is correct
6 Correct 41 ms 43228 KB Output is correct
7 Correct 38 ms 42704 KB Output is correct
8 Correct 40 ms 43100 KB Output is correct
9 Correct 41 ms 43384 KB Output is correct
10 Correct 38 ms 42716 KB Output is correct
11 Correct 192 ms 54516 KB Output is correct
12 Correct 400 ms 63136 KB Output is correct
13 Incorrect 645 ms 87348 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 43000 KB Output is correct
2 Correct 41 ms 43176 KB Output is correct
3 Correct 39 ms 43152 KB Output is correct
4 Correct 39 ms 42616 KB Output is correct
5 Correct 39 ms 42580 KB Output is correct
6 Correct 41 ms 43228 KB Output is correct
7 Correct 38 ms 42704 KB Output is correct
8 Correct 40 ms 43100 KB Output is correct
9 Correct 41 ms 43384 KB Output is correct
10 Correct 38 ms 42716 KB Output is correct
11 Correct 192 ms 54516 KB Output is correct
12 Correct 400 ms 63136 KB Output is correct
13 Incorrect 645 ms 87348 KB Output isn't correct
14 Halted 0 ms 0 KB -