Submission #1074053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074053		pravcoder	Tropical Garden (IOI11_garden)	C++17	49 / 100	5091 ms	3420 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> v2i;
typedef pair<int, int> pi;
typedef vector<pi> vpi;

#define pb push_back
#define mp make_pair
#define rept(i, a, b) for (int i = a; i < b; i++)
#define rep(i, n) for (int i = 0; i < n; i++)

int n, m, p, q;
vpi r;
vpi o; //outgoing trails from each fountain: best then second best
int k;

bool dfs(int u, int par = -2, int d = 0) {
	if (d == k) {
		//cout << "Ended at node " << u << "\n";
		return (u == p);
	}
	else {
		int v;
		if (o[u].first != par || o[u].second == -1) v = o[u].first;
		else v = o[u].second;
		//cout << "Travelled to node " << v << "\n";
		return dfs(v, u, d + 1);
	}
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	n = N, m = M, p = P, q = Q;
	o.resize(N, { -1, -1 });
	rep(i, M) {
		int start = R[i][0], end = R[i][1];
		r.pb({ start, end });
		rep(j, 2) {
			if (j == 1) swap(start, end);
			if (o[start].first == -1) {
				o[start].first = end;
			}
			else if (o[start].second == -1) {
				o[start].second = end;
			}
		}
	}


	/*cout << "Best options:\n";
	rep(i, N) {
		printf("%d: %d %d\n", i, o[i].first, o[i].second);
	}*/

	rep(i, Q) {
		k = G[i];
		int ans = 0;
		rep(s, N) {
			//cout << "Search from " << s << ":\n";
			ans += dfs(s);
		}
		answer(ans);
	}
}

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