Submission #851275

#	Time	Username	Problem	Language	Result	Execution time	Memory
851275		Halym2007	Tropical Garden (IOI11_garden)	C++11	69 / 100	5034 ms	83272 KiB

garden

#include <bits/stdc++.h>
using namespace std;
const int LOG = 30;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define MAXM 150005
#define sz size()
#include "garden.h"
#include "gardenlib.h"

pair <int, int> dp1[MAXM][LOG], dp2[MAXM][LOG];
vector <int> adj[MAXM];

//void answer(int x) {
//	cout << x << " ";
//}


void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
	for (int i = 0; i < M; ++i) {
		int u = R[i][0], v = R[i][1];
		adj[u].pb (v);
		adj[v].pb (u);
	}
	for (int i = 0; i < N; ++i) {
		if ((int)adj[i].sz) {
			dp1[i][0].ff = adj[i][0];
			dp1[i][0].ss = i;
			if ((int)adj[i].sz > 1) {
				dp2[i][0].ff = adj[i][1];
				dp2[i][0].ss = i;
			}
			else dp2[i][0] = dp1[i][0];
		}
	}
	
	for (int j = 1; j < LOG; ++j) {
		for (int i = 0; i < N; ++i) {
			int x = dp1[i][j - 1].ff;
			int y = dp1[i][j - 1].ss;
			if (adj[x][0] == y) {
				dp1[i][j] = dp2[x][j - 1];
			}
			else {
				dp1[i][j] = dp1[x][j - 1];
			}
			
			x = dp2[i][j - 1].ff;
			y = dp2[i][j - 1].ss;
			if (adj[x][0] == y) {
				dp2[i][j] = dp2[x][j - 1];
			}
			else {
				dp2[i][j] = dp1[x][j - 1];
			}
		}
	}
	for (int ii = 0; ii < Q; ++ii) {
		int val = G[ii];
		int jogap = 0;
		for (int i = 0; i < N; ++i) {
			int hp = i;
			int pr = -1;
			for (int j = LOG - 1; j >= 0; j--) {
				if (val>>j&1) {
					if (adj[hp][0] == pr) {
						auto tr = dp2[hp][j];
						hp = tr.ff;
						pr = tr.ss;
					}
					else {
						auto tr = dp1[hp][j];
						hp = tr.ff;
						pr = tr.ss;
					}
				} 
			}	
			if (hp == P) { 
				jogap++;
			}
		}
		answer (jogap);
	}
}




//
//#include <stdio.h>
//#include <stdlib.h>
//
//#define MAX_M  1000000
//#define MAX_Q  2000
//
//static int N, M, P, Q;
//static int R[MAX_M][2];
//static int G[MAX_Q];
//
//void read_input()
//{
//  int i;
//  scanf("%d %d %d",&N,&M,&P);
//  for(i=0; i<M; i++)
//    scanf("%d %d",&R[i][0],&R[i][1]);
//  scanf("%d",&Q);
//  for(i=0; i<Q; i++)
//    scanf("%d",&G[i]);
//}
//
//
//
//int main() {
//	freopen("input.txt", "r", stdin);
//  read_input();
//  count_routes(N,M,P,R,Q,G);
//  return 0;
//}

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