제출 #1267371

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1267371		nickolasarapidis	Tropical Garden (IOI11_garden)	C++20	0 / 100	16 ms	36672 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

const int MAXN = 150000, MAXL = 30;

int anc[2*MAXN][MAXL], par[2*MAXN], parF[MAXN], parS[MAXN], P1, P2;

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	memset(par, -1, sizeof(par));
	memset(anc, -1, sizeof(anc));
	P1 = P;
	P2 = P + N;
	vector<int> adj[N];
	for(int i = 0; i < M; i++){
		adj[R[i][0]].pb(R[i][1]);
		adj[R[i][1]].pb(R[i][0]);
	}
	for(int i = 0; i < N; i++){
		if(adj[i].size() == 1) adj[i].pb(adj[i][0]);
		parF[i] = adj[i][0];
		parS[i] = adj[i][1];
	}
	for(int i = 0; i < N; i++){
		if(adj[i][0] != adj[i][1]){
			par[i] = parF[i];
			if(i == parF[parS[i]]) par[i + N] = parS[i] + N;
			else par[i + N] = parS[i];
		}
		else{
			par[i] = parF[i] + N;
		}
	}
	for(int i = 0; i < 2*N; i++){
		anc[i][0] = par[i];
	}
	for(int i = 1; i < MAXL; i++){
		for(int x = 0; x < 2*N; x++){
			anc[x][i] = anc[anc[x][i - 1]][i - 1];
		}
	}
	for(int k = 0; k < Q; k++){
		int K = G[k], ans = 0;
		for(int j = 0; j < N; j++){
			int ret = j;
			for(int i = 0; i < MAXL; i++){
				if(K&(1 << i)){
					ret = anc[ret][i];
				}
			}
			if(ret == P1 or ret == P2){
				ans++;
			}
		}
		answer(ans);
	}
}

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