Submission #302640

#	Time	Username	Problem	Language	Result	Execution time	Memory
302640		errorgorn	Tropical Garden (IOI11_garden)	C++11	69 / 100	5046 ms	199544 KiB

garden

#include "garden.h"
#include "gardenlib.h"

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second

#define rep(x,start,end) for(auto x=start;x!=end;x++)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

int n,m,k,q;
vector<int> al[150005];
int v[300005];
int par[32][300005];

int nxt[8][16][300005];

int node[150005];

void count_routes(int N, int M, int P, int R[][2], int Q, int g[]){
	n=N,m=M,k=P,q=Q;
	
	rep(x,0,m){
		al[R[x][0]].push_back(x*2);
		al[R[x][1]].push_back(x*2+1);
		
		v[x*2]=R[x][1];
		v[x*2+1]=R[x][0];
	}
	
	rep(x,0,m*2){
		if (sz(al[v[x]])==1 || (al[v[x]][0]>>1)!=(x>>1)) par[0][x]=al[v[x]][0];
		else par[0][x]=al[v[x]][1];
	}
	
	//rep(x,0,m*2) cout<<nxt[0][x]<<endl;
	
	rep(layer,0,31){
		rep(x,0,m*2){
			par[layer+1][x]=par[layer][par[layer][x]];
		}
	}
	
	rep(layer,0,8){
		rep(bm,0,16){
			rep(x,0,m*2){
				int curr=x;
				rep(bit,0,4) if (bm&(1<<bit)){
					curr=par[layer*4+bit][curr];
				}
				nxt[layer][bm][x]=curr;
			}
		}
	}
	
	rep(x,0,q){
		int ans=0;
		g[x]--;
		
		rep(y,0,n) node[y]=al[y][0];
		
		rep(layer,0,8){
			int *arr=nxt[layer][g[x]&15];
			rep(y,0,n) node[y]=arr[node[y]];
			g[x]>>=4;
		}
		
		rep(y,0,n) if (v[node[y]]==k) ans++;
		
		answer(ans);
	}
}

Compilation message (stderr)

garden.cpp:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
garden.cpp:6: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      |

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