oj.uz

Submission #105938

# Submission time Handle Problem Language Result Execution time Memory
105938 2019-04-15T19:29:51 Z tincamatei Tropical Garden (IOI11_garden) C++14
49 / 100
 5000 ms 9336 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 150000;
const int MAX_M = 150000;

struct Edge {
	int a, b;

	inline int other(int x) {
		return a ^ b ^ x;
	}
} edges[MAX_M];

vector<int> graph[MAX_N];
vector<int> realgraph[MAX_N];

int rushnode(int nod, int x, int lastedge) {
	if(x == 0)
		return nod;
	for(auto it: realgraph[nod])
		if(it != lastedge)
			return rushnode(edges[it].other(nod), x - 1, it);
	return rushnode(edges[realgraph[nod][0]].other(nod), x - 1, realgraph[nod][0]);
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  int i;
	
	for(int i = 0; i < M; ++i) {
		edges[i] = {R[i][0], R[i][1]};
		graph[R[i][0]].push_back(i);
		graph[R[i][1]].push_back(i);
	}

	for(int i = 0; i < N; ++i) {
		sort(graph[i].begin(), graph[i].end());
		for(int j = 0; j < 2 && j < graph[i].size(); ++j)
			realgraph[i].push_back(graph[i][j]);
	}
	
	int rez = 0;
	for(int i = 0; i < N; ++i)
		if(rushnode(i, G[0], -1) == P)
			++rez;
  for(i=0; i<Q; i++)
    answer(rez);
}

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:41:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < 2 && j < graph[i].size(); ++j)
                           ~~^~~~~~~~~~~~~~~~~

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7388 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 10 ms 7500 KB Output is correct
4 Correct 9 ms 7420 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 10 ms 7544 KB Output is correct
7 Correct 9 ms 7336 KB Output is correct
8 Correct 10 ms 7416 KB Output is correct
9 Correct 13 ms 7800 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7388 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 10 ms 7500 KB Output is correct
4 Correct 9 ms 7420 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 10 ms 7544 KB Output is correct
7 Correct 9 ms 7336 KB Output is correct
8 Correct 10 ms 7416 KB Output is correct
9 Correct 13 ms 7800 KB Output is correct
10 Correct 18 ms 7416 KB Output is correct
11 Execution timed out 5027 ms 9336 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7388 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 10 ms 7500 KB Output is correct
4 Correct 9 ms 7420 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 10 ms 7544 KB Output is correct
7 Correct 9 ms 7336 KB Output is correct
8 Correct 10 ms 7416 KB Output is correct
9 Correct 13 ms 7800 KB Output is correct
10 Correct 18 ms 7416 KB Output is correct
11 Execution timed out 5027 ms 9336 KB Time limit exceeded
12 Halted 0 ms 0 KB -