Submission #105938

#	Time	Username	Problem	Language	Result	Execution time	Memory
105938		tincamatei	Tropical Garden (IOI11_garden)	C++14	49 / 100	5027 ms	9336 KiB

garden

#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 (stderr)

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 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31