oj.uz

Submission #1074053

# Submission time Handle Problem Language Result Execution time Memory
1074053 2024-08-25T07:22:55 Z pravcoder Tropical Garden (IOI11_garden) C++17
49 / 100
 5000 ms 3420 KB 
#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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Execution timed out 5091 ms 3420 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Execution timed out 5091 ms 3420 KB Time limit exceeded
12 Halted 0 ms 0 KB -