Submission #236866

#	Time	Username	Problem	Language	Result	Execution time	Memory
236866		kostia244	Tropical Garden (IOI11_garden)	C++17	100 / 100	4853 ms	38648 KiB

garden

#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx2,avx,sse,sse2,ssse3,tune=native,popcnt")
#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 300500, mlg = 30;
int up[mlg][maxn], 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];
		if(cnt[f] < 2) up[0][2*f + cnt[f]] = 2*t + (cnt[t]==0);
		if(cnt[t] < 2) up[0][2*t + cnt[t]] = 2*f + (cnt[f]==0);
		cnt[f]++, cnt[t]++;
	}
	for(int i = 0; i < 2*n; i++) if(up[0][i] < 0) up[0][i] = up[0][i^1];
	for(int i = 1; i < mlg; i++)
		for(int j = 0; j < 2*n; j++)
			up[i][j] = up[i-1][up[i-1][j]];
	for(int I = 0; I < Q; I++) {
		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)
			for(int j = 0; j < 2*n; j+=2)
				cnt[j] = up[i][cnt[j]];
		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: 31 / 31