Submission #236847

#	Time	Username	Problem	Language	Result	Execution time	Memory
236847		kostia244	Tropical Garden (IOI11_garden)	C++17	69 / 100	5064 ms	39744 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 300500, mlg = 30;
int up[maxn][mlg], cnt[maxn];
void count_routes(int n, int m, int P, int R[][2], int Q, int G[]) {
	memset(cnt, 0, sizeof cnt);
	memset(up, -1, sizeof up);
	for(int i = 0; i < m; i++) {
		int f = R[i][0], t = R[i][1];
		//cout << f << " " << t << " " << i << '\n';
		if(cnt[f] < 2) up[2*f + cnt[f]][0] = 2*t + (cnt[t]==0);//, cout << 2*f + cnt[f] << " -- " << 2*t + (cnt[t]==0) << '\n';
		if(cnt[t] < 2) up[2*t + cnt[t]][0] = 2*f + (cnt[f]==0);//, cout << 2*t + cnt[t] << " -- " << 2*f + (cnt[f]==0) << '\n';
		cnt[f]++, cnt[t]++;
	}
	for(int i = 0; i < 2*n; i++) if(up[i][0] < 0) up[i][0] = up[i^1][0];
	for(int i = 1; i < mlg; i++)
		for(int j = 0; j < 2*n; j++)
			up[j][i] = up[up[j][i-1]][i-1];
	//for(int i = 0; i < 2*n; i++) cout << i << " = " << up[i][0] << "\n";
	for(int I = 0; I < Q; I++) {
		//cout << P << " " << G[I] << '\n';
		int ans = 0;
		for(int i = 0; i < 2*n; i+=2) cnt[i] = i;
		for(int i = 0; i < mlg; i++) {
			if(!((G[I]>>i)&1)) continue;
			for(int j = 0; j < 2*n; j+=2) {
				cnt[j] = up[cnt[j]][i];
			}
		}
		for(int i = 0; i < 2*n; i+=2) ans += cnt[i] == 2*P || cnt[i] == 2*P+1;
		answer(ans);
	}
}

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