제출 #216170

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
216170		AQT	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	0 / 100	9 ms	7680 KiB

garden

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

using namespace std;

int N, M, P, Q;
int beau[2][150005];
int nxt[300005];
bool island[300005];
int hasP[300005];
int cyc[2];
int dist[2][300005];
int par[2][300005];
int rem[2][300005];
vector<int> graph[300005];
vector<int> c[2];

/*
void answer(int X){
	
}
*/

void dfs(int n, int b, int rt){
	hasP[n] |= b;
	for(int e : graph[n]){
		if(!(hasP[e]&b)){
			dist[b-1][e] = dist[b-1][n] + 1;
			par[b-1][e] = n;
			dfs(e, b, rt);
		}
		else{
			cyc[b] = dist[b-1][n] + 1;
			c[b-1].emplace_back(e);
			int crnt = e;
			int cnt = 0;
			while(crnt != rt){
				rem[b-1][crnt] = ++cnt;
				crnt = par[b-1][crnt];
				c[b-1].emplace_back(e);
			}
		}
	}
}

void bfs(int b){
	queue<int> qu;
	for(int n : c[b]){
		dist[b][n] = 0;
		par[b][n] = n;
		qu.push(n);
	}
	while(qu.size()){
		int n = qu.front();
		qu.pop();
		for(int e : graph[n]){
			if(dist[b][e] > dist[b][n] + 1){
				dist[b][e] = dist[b][n] + 1;
				par[b][e] = par[b][n];
				qu.push(e);
			}
		}
	}
}

void count_routes(int NN, int MM, int PP, int R[][2], int QQ, int G[]){
	N = NN, M = MM, P = PP, Q = QQ;
	for(int i = M; i; i--){
		beau[1][R[i-1][0]] = beau[0][R[i-1][0]];
		beau[0][R[i-1][0]] = i;
		beau[1][R[i-1][1]] = beau[0][R[i-1][1]];
		beau[0][R[i-1][1]] = i;
	}
	for(int i = 0; i<N; i++){
		if(!beau[0][i]){
			island[i+N] = island[i] = 1;
			continue;
		}
		else if(!beau[1][i]){
			int n = (R[beau[0][i]][0] == i ? R[beau[0][i]][1] : R[beau[0][i]][0]);
			nxt[i+N] = nxt[i] = n + (beau[0][n] == beau[0][i])*N;
			graph[n + (beau[0][n] == beau[0][i])*N].emplace_back(i);
			graph[n + (beau[0][n] == beau[0][i])*N].emplace_back(i+N);
		}
		else{
			int n = (R[beau[0][i]][0] == i ? R[beau[0][i]][1] : R[beau[0][i]][0]);
			nxt[i] = n + (beau[0][n] == beau[0][i])*N;
			graph[n + (beau[0][n] == beau[0][i])*N].emplace_back(i);
			n = (R[beau[1][i]][0] == i ? R[beau[1][i]][1] : R[beau[1][i]][0]);
			nxt[i+N] = n;
			graph[n].emplace_back(i+N);
		}
	}
	dfs(P, 1, P);
	dfs(P+N, 2, P+N);
	fill(dist[0], dist[0]+2*N, 6*N);
	fill(dist[1], dist[1]+2*N, 6*N);
	if(c[0].empty()){
		c[0].push_back(P);
	}
	if(c[1].empty()){
		c[1].push_back(P+N);
	}
	bfs(0);
	bfs(1);	
	for(int q = 0; q<Q; q++){
		int k = G[q];
		int ans = 0;
		for(int i =0 ; i<N; i++){
			bool good = 0;
			if((hasP[i]&1) && k >= dist[0][i]){
				if(cyc[0]){
					good = (rem[0][par[0][i]] == (k-dist[0][i])%cyc[0]);
				}
				else{
					good = (dist[0][i] == k);
				}
			}
			if(!good && (hasP[i]&2) && k >= dist[1][i]){
				if(cyc[1]){
					good = (rem[1][par[1][i]] == (k-dist[1][i])%cyc[1]);
				}
				else{
					good = (dist[1][i] == k);
				}
			}
			ans += good;
		}
		answer(ans);
	}
}
/*
int main(){
	
}
*/

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