Submission #147229

#	Time	Username	Problem	Language	Result	Execution time	Memory
147229		jhwest2	Tropical Garden (IOI11_garden)	C++14	69 / 100	5048 ms	28880 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef pair<int, int> pii;

const int MAX = 150101;
vector<int> arr[MAX];
vector<int> edge[MAX*2];
pii dist[2*MAX];
bool chk[2*MAX];
queue<pii> q;

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

	 for (int i=0; i<=N; i++) {
	 	while (arr[i].size() != 2)
	 		arr[i].push_back(N);
	 }

	 for (int i=0; i<N; i++) {
	 	if (arr[i][1] == N) {
	 		if (arr[arr[i][0]][0] == i) {
	 			edge[N+arr[i][0]].push_back(i);
	 			edge[N+arr[i][0]].push_back(N+i);
	 		}
	 		else {
	 			edge[arr[i][0]].push_back(i);
	 			edge[arr[i][0]].push_back(N+i);
	 		}
	 		continue;
	 	}
	 	if (arr[arr[i][0]][0] == i)
	 		edge[N+arr[i][0]].push_back(i);
	 	else
	 		edge[arr[i][0]].push_back(i);

	 	if (arr[arr[i][1]][0] == i)
	 		edge[N+arr[i][1]].push_back(N+i);
	 	else
	 		edge[arr[i][1]].push_back(N+i);
	 }

	 memset(dist, -1, sizeof dist);

	 q.push(pii(P, 0));
	 while (!q.empty()) {
	 	pii tmp = q.front();
	 	q.pop();

	 	if (chk[tmp.va]) continue;
	 	if (tmp.vb != 0) {
	 		chk[tmp.va] = true;
	 		dist[tmp.va].va = tmp.vb;
	 	}

	 	for (int i=0; i<edge[tmp.va].size(); i++)
	 		q.push(pii(edge[tmp.va][i], tmp.vb+1));
	 }

	 memset(chk, false, sizeof chk);
	 q.push(pii(N+P, 0));
	 while (!q.empty()) {
	 	pii tmp = q.front();
	 	q.pop();

	 	if (chk[tmp.va]) continue;
	 	if (tmp.vb != 0) {
	 		chk[tmp.va] = true;
	 		dist[tmp.va].vb = tmp.vb;
	 	}

	 	for (int i=0; i<edge[tmp.va].size(); i++)
	 		q.push(pii(edge[tmp.va][i], tmp.vb+1));
	 }

	 for (int i=0; i<Q; i++) {
	 	int mod = dist[P].va;
	 	int ans = 0;
	 	for (int j=0; j<N; j++) {
	 		if (dist[j].va == -1) continue;
	 		if ((G[i] > dist[j].va && mod != -1 && G[i]%mod == dist[j].va%mod) || G[i] == dist[j].va) ++ans;
	 	}

	 	mod = dist[N+P].vb;
	 	for (int j=0; j<N; j++) {
	 		if (dist[j].vb == -1) continue;
	 		if ((G[i] > dist[j].vb && mod != -1 && G[i]%mod == dist[j].vb%mod) || G[i] == dist[j].vb) ++ans;
	 	}

	 	answer(ans);
	 }
	 return;
}

Compilation message (stderr)

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:65:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i=0; i<edge[tmp.va].size(); i++)
                  ~^~~~~~~~~~~~~~~~~~~~
garden.cpp:81:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i=0; i<edge[tmp.va].size(); i++)
                  ~^~~~~~~~~~~~~~~~~~~~

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