Submission #24885

#	Time	Username	Problem	Language	Result	Execution time	Memory
24885		Hiasat	Tropical Garden (IOI11_garden)	C++14	49 / 100	68 ms	34552 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MX = 150011;
vector<int> adj[MX * 2], g[MX * 2];
int C[MX*2];

int need[MX * 2][2];

void connect(int u , int v, int N) {
	if (adj[u][0] == v || adj[u][0] == v - N)
		u = u + N;
	g[u].push_back(v);
}
int _P,_N;

void dfs(int u , int cost, int it) {
	if (need[u][it] != -1)
		return;
	need[u][it] = cost;
	for (int i = 0; i < g[u].size(); ++i) {
		if(g[u][i] == _P || g[u][i] == _P + _N){
			C[g[u][i]] = cost + 1;
		}

		dfs(g[u][i], cost + 1, it);
	}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
	_N = N;
	_P = P;
	memset(need, -1, sizeof need);
	memset(C, -1, sizeof C);
	for (int i = 0; i < M; ++i) {
		adj[R[i][0]].push_back(R[i][1]);
		adj[R[i][1]].push_back(R[i][0]);
	}
	for (int i = 0; i < N; ++i) {
		while (adj[i].size() > 2)
			adj[i].pop_back();
		if (adj[i].size())
			connect(adj[i][0], i, N);
		if (adj[i].size()) {
			if (adj[i].size() == 2) {
				connect(adj[i][1], i + N, N);
			} else {
				connect(adj[i][0], i + N, N);
			}
		}
	}
	dfs(P, 0, 0);
	dfs(P + N, 0, 1);
/*	
	for (int i = 0; i < N; ++i){
		cout << need[i][0] << " " << need[i][1] << endl;
	}*/
	for (int k = 0 ; k < Q ; k++) {
		int res = 0;
		for (int i = 0; i < N; ++i) {
			for (int it = 0 ; it < 2 ; it++) {
				if(need[i][it] == -1)
					continue;
				int rem = G[k];
				if(rem < need[i][it])
					continue;
				rem -= need[i][it];

				if(rem == 0 || (C[P+it*N] != -1 && rem%C[P+it*N] == 0)){
					res++;
					break;
				}
			}
		}
		answer(res);
	}
}

Compilation message (stderr)

garden.cpp: In function 'void dfs(int, int, int)':
garden.cpp:26:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[u].size(); ++i) {
                  ~~^~~~~~~~~~~~~

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