Submission #347844

#	Time	Username	Problem	Language	Result	Execution time	Memory
347844		tengiz05	Tropical Garden (IOI11_garden)	C++17	49 / 100	111 ms	27372 KiB

garden

#include "garden.h"
#include "gardenlib.h"
//~ #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pb push_back
const int N_ = 150005;
int ans, n, m, target;
vector<int> edges[N_];
int d;
int nxt[N_*2][30];

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	target = P;
	n = N, m = M;
	for(int i=0;i<m;i++){
		if(edges[R[i][0]].size() < 2)edges[R[i][0]].pb(R[i][1]);
		if(edges[R[i][1]].size() < 2)edges[R[i][1]].pb(R[i][0]);
	}
	for(int i=0;i<n*2;i++){
		nxt[i][0] = -1;
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<(int)edges[i].size();j++){
			int to = edges[i][j];
			if(edges[to][0] == i && edges[to].size() == 2){
				nxt[i+j*n][0] = to+n;
			}else {
				nxt[i+j*n][0] = to;
			}
		}
	}
	for(int i=1;i<30;i++){
		for(int u=0;u<n*2;u++){
			if(~nxt[u][0])nxt[u][i] = nxt[nxt[u][i-1]][i-1];
			else nxt[u][i] = -1;
		}
	}
	for(int q=0;q<Q;q++){
		int t = G[q];
		int ans = 0;
		for(int i=0;i<n;i++){
			int s = i;
			if(nxt[i][0] == -1)continue;
			for(int j=0;j<29;j++){
				if((1<<j)&t)s = nxt[s][j];
			}ans += (s == P || s == P+n);
		}answer(ans);
	}return;
}

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