제출 #302632

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
302632		errorgorn	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	69 / 100	5028 ms	199000 KiB

garden

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

#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)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++: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];

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){
			int curr=al[y][0];
			int bm=g[x];		
			rep(layer,0,8){
				curr=nxt[layer][bm&15][curr];
				bm>>=4;
			}
			if (v[curr]==k) ans++;
		}
		
		answer(ans);
	}
}

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