Submission #1268004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268004		nickolasarapidis	Tropical Garden (IOI11_garden)	C++20	0 / 100	2 ms	576 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 par[2*MAXN], parF[MAXN], parS[MAXN], P1, P2, length = -1, dis1[MAXN], dis2[MAXN];
vector<int> adj[2*MAXN];
bool b1 = false, b2 = false;

void dfs1(int s, int e, int d){
	if(s == P1 and e != -1){
		length = d;
		b1 = true;
		return;
	}
	dis1[s] = d;
	for(auto u : adj[s]){
		dfs1(u, s, d + 1);
	}
}

void dfs2(int s, int e, int d){
	if(s == P2 and e != -1){
		length = d;
		b2 = true;
		return;
	}
	dis2[s] = d;
	for(auto u : adj[s]){
		dfs2(u, s, d + 1);
	}
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	P1 = P;
	P2 = P + 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];
		adj[i].clear();
	}
	for(int i = 0; i < N; i++){
		if(i == parF[parF[i]]){
			par[i] = parF[i] + N;
			par[parF[i]] = i + N;
		}
		else{
			par[i] = parF[i];
		}
		if(i == parF[parS[i]]){
			par[i + N] = parS[i] + N;
		}
		else{
			par[i + N] = parS[i];
		}
	}
	for(int i = 0; i < 2*N; i++){
		adj[par[i]].pb(i);
	}
	dfs1(P1, -1, 0);
	dfs2(P2, -1, 0);
	for(int k = 0; k < Q; k++){
		int K = G[k], ans = 0;
		for(int i = 0; i < N; i++){
			int X = K;
			if(b1){
				X -= dis1[i];
				if(X%length == 0) ans++;
			}
			else{
				if(dis1[i] == X) ans++;
			}
			X = K;
			if(b2){
				X -= dis2[i];
				if(X%length == 0) ans++;
			}
			else{
				if(dis2[i] == X) ans++;
			}
		}
		answer(ans);
	}
}

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