oj.uz

Submission #24885

# Submission time Handle Problem Language Result Execution time Memory
24885 2017-06-16T20:15:30 Z Hiasat Tropical Garden (IOI11_garden) C++14
49 / 100
 68 ms 34552 KB 
#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

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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18032 KB Output is correct
2 Correct 19 ms 18040 KB Output is correct
3 Correct 19 ms 18012 KB Output is correct
4 Correct 18 ms 17996 KB Output is correct
5 Correct 19 ms 17928 KB Output is correct
6 Correct 19 ms 18168 KB Output is correct
7 Correct 18 ms 17912 KB Output is correct
8 Correct 19 ms 18012 KB Output is correct
9 Correct 21 ms 18256 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18032 KB Output is correct
2 Correct 19 ms 18040 KB Output is correct
3 Correct 19 ms 18012 KB Output is correct
4 Correct 18 ms 17996 KB Output is correct
5 Correct 19 ms 17928 KB Output is correct
6 Correct 19 ms 18168 KB Output is correct
7 Correct 18 ms 17912 KB Output is correct
8 Correct 19 ms 18012 KB Output is correct
9 Correct 21 ms 18256 KB Output is correct
10 Correct 19 ms 17980 KB Output is correct
11 Correct 35 ms 19832 KB Output is correct
12 Correct 56 ms 20920 KB Output is correct
13 Incorrect 68 ms 34552 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18032 KB Output is correct
2 Correct 19 ms 18040 KB Output is correct
3 Correct 19 ms 18012 KB Output is correct
4 Correct 18 ms 17996 KB Output is correct
5 Correct 19 ms 17928 KB Output is correct
6 Correct 19 ms 18168 KB Output is correct
7 Correct 18 ms 17912 KB Output is correct
8 Correct 19 ms 18012 KB Output is correct
9 Correct 21 ms 18256 KB Output is correct
10 Correct 19 ms 17980 KB Output is correct
11 Correct 35 ms 19832 KB Output is correct
12 Correct 56 ms 20920 KB Output is correct
13 Incorrect 68 ms 34552 KB Output isn't correct
14 Halted 0 ms 0 KB -