제출 #23673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
23673		Hiasat	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	69 / 100	5050 ms	124580 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

vector< pii > g[150001];

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

ll need[150001][2][2];

void bld(int N, int P, int state) {
	memset(dp, -1, sizeof dp);
	memset(last,-1,sizeof last);
	memset(mx, 0, sizeof mx);
	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) {
				if (state == 0) {
					mx[i][0][0] = g[P][0].second != g[i][0].second;
				} else {
					mx[i][0][0] = g[P][0].second == g[i][0].second;
				}

			}
		}
		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) {
				if (state == 0) {
					mx[i][1][0] = g[P][0].second != g[i][1].second;
				} else {
					mx[i][1][0] = g[P][0].second == g[i][1].second;
				}
			}
		}
	}
	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]);
				}
			}
		}
}
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(need, -1, sizeof need);
	
	for (int state = 0 ; state < 2 ; state++) {
		bld(N, P, state);
		for (int i = 0 ; i < N ; i++) {
			for (int it = 0 ; it < 2 ; it++) {
				int go = i;
				int lastEdge = -1;
				if (it && g[i].size())
					lastEdge = g[i][0].second;
				ll t = 0;
				for (int k = 30 ; k >= 0 ; k--) {
					if (!mx[go][lastEdge == g[go][0].second][k]) {
						t += (1 << k);
						int nw = dp[go][lastEdge == g[go][0].second][k];
						lastEdge = last[go][lastEdge == g[go][0].second][k];
						go = nw;
					}
				}
				if (dp[go][lastEdge == g[go][0].second][0] == P) {
					need[i][it][state] = t + 1;
				}
			}
		}
	}
	for (int i = 0 ; i < Q ; i++) {
		int cnt = 0;
		for (int j = 0 ; j < N ; j++) {
			for (int state = 0 ; state < 2 ; state++) {
				if (need[j][0][state] == -1)
					continue;
				if (G[i] < need[j][0][state])
					continue;
				ll rem = G[i] - need[j][0][state];
				if(rem == 0){

					cnt++;
					break;
				} else if (need[P][state][state] != -1 && rem%need[P][state][state] == 0){
					cnt++;
					break;
				}
			}
		}
		answer(cnt);
	}
}

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