oj.uz

Submission #236853

# Submission time Handle Problem Language Result Execution time Memory
236853 2020-06-03T15:10:18 Z srvlt Tropical Garden (IOI11_garden) C++14
100 / 100
 3540 ms 116976 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#define ll long long
#define ull unsigned long long
#define db long double
#define pb push_back
#define ppb pop_back
#define F first
#define S second
#define mp make_pair
#define all(x) (x).begin(), (x).end()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;

typedef tree <pii, null_type, less <pii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int max_N = 500007;
int n, m, p, cnt;
vi adj[max_N], g[max_N], gr[max_N];
pii edge[max_N], E[max_N];
map <pii, int> ind;

int zero[max_N], used[max_N], par[max_N], cyc[max_N], h[max_N];
vi bad, vec;

void dfs(int v) {
	used[v] = 1;
	for (int to : g[v]) {
		if (used[to] == 1) {
			int u = v, len = 1;
			vec.clear();
			while (u != to) {
				if (E[u].F == p) {
					vec.pb(u);
				}
				u = par[u];
				len++;
			}
			if (E[to].F == p) {
				vec.pb(to);
			}
			for (int i : vec) {
				cyc[i] = len;
			}
		}
		if (used[to] == 0) {
			par[to] = v;
			dfs(to);
		}
	}
	used[v] = 2;
}

void go(int v) {
	for (int to : gr[v]) {
		h[to] = h[v] + 1;
		go(to);
	}
}

int dist[2][max_N];
queue <int> q;

void bfs(int c, int s) {
	memset(& used, 0, sizeof(used));
	q.push(s);
	used[s] = 1;
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		for (int to : gr[v]) {
			if (!used[to]) {
				used[to] = 1;
				dist[c][to] = dist[c][v] + 1;
				q.push(to);
			}
		}
	}
}

int get_end(int v, int e) {
	return edge[e].F + edge[e].S - v;
}

int get(int k) {
	int res = 0;
	for (int i = 0; i < n; i++) {
		if (h[zero[i]] == k) {
			res++;
			continue;
		}
		for (int j = 0; j < (int)bad.size(); j++) {
			int c = cyc[bad[j]], d = dist[j][zero[i]];
			if (d == 0) {
				continue;
			}
			assert(c > 0);
			if (k >= d && (k - d) % c == 0) {
				res++;
				break;
			}
		}
	}
	return res;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
	n = N, m = M, p = P;
	for (int i = 0; i < m; i++) {
		adj[R[i][0]].pb(i + 1);
		adj[R[i][1]].pb(i + 1);
		edge[i + 1] = {R[i][0], R[i][1]};
	}
	for (int i = 0; i < n; i++) {
		E[cnt] = {i, 0};
		ind[{i, 0}] = cnt++;
		for (int j : adj[i]) {
			E[cnt] = {i, j};
			ind[{i, j}] = cnt++;
		}
	}
	for (int i = 0; i < n; i++) {
		int to = get_end(i, adj[i][0]);
		g[ind[{i, 0}]].pb(ind[{to, adj[i][0]}]);
		for (int j : adj[i]) {
			int tmp = (j == adj[i][0] && (int)adj[i].size() > 1);
			to = get_end(i, adj[i][tmp]);
			g[ind[{i, j}]].pb(ind[{to, adj[i][tmp]}]);
		}
	}
	for (int i = 0; i < cnt; i++) {
		for (int j : g[i]) {
			gr[j].pb(i);
		}
	}
	for (int i = 0; i < cnt; i++) {
		if (used[i] == 0) {
			par[i] = -1;
			dfs(i);
		}
	}
	for (int i : adj[p]) {
		int v = ind[{p, i}];
		if (cyc[v]) {
			bad.pb(v);
		}	else {
			go(v);
		}
	}
	assert((int)bad.size() <= 2);
	for (int i = 0; i < (int)bad.size(); i++) {
		bfs(i, bad[i]);
	}
	for (int i = 0; i < cnt; i++) {
		if (E[i].S == 0) {
			zero[E[i].F] = i;
		}
	}
	for (int i = 0; i < Q; i++) {
		answer(get(G[i]));
	}
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 38016 KB Output is correct
2 Correct 29 ms 38016 KB Output is correct
3 Correct 29 ms 38144 KB Output is correct
4 Correct 27 ms 37624 KB Output is correct
5 Correct 26 ms 37632 KB Output is correct
6 Correct 29 ms 38400 KB Output is correct
7 Correct 27 ms 37624 KB Output is correct
8 Correct 29 ms 38064 KB Output is correct
9 Correct 39 ms 40056 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 38016 KB Output is correct
2 Correct 29 ms 38016 KB Output is correct
3 Correct 29 ms 38144 KB Output is correct
4 Correct 27 ms 37624 KB Output is correct
5 Correct 26 ms 37632 KB Output is correct
6 Correct 29 ms 38400 KB Output is correct
7 Correct 27 ms 37624 KB Output is correct
8 Correct 29 ms 38064 KB Output is correct
9 Correct 39 ms 40056 KB Output is correct
10 Correct 27 ms 37632 KB Output is correct
11 Correct 83 ms 47756 KB Output is correct
12 Correct 180 ms 58360 KB Output is correct
13 Correct 234 ms 87960 KB Output is correct
14 Correct 656 ms 100508 KB Output is correct
15 Correct 728 ms 104312 KB Output is correct
16 Correct 564 ms 90356 KB Output is correct
17 Correct 523 ms 88848 KB Output is correct
18 Correct 189 ms 56800 KB Output is correct
19 Correct 669 ms 101628 KB Output is correct
20 Correct 720 ms 104312 KB Output is correct
21 Correct 577 ms 90224 KB Output is correct
22 Correct 550 ms 90232 KB Output is correct
23 Correct 679 ms 103544 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 38016 KB Output is correct
2 Correct 29 ms 38016 KB Output is correct
3 Correct 29 ms 38144 KB Output is correct
4 Correct 27 ms 37624 KB Output is correct
5 Correct 26 ms 37632 KB Output is correct
6 Correct 29 ms 38400 KB Output is correct
7 Correct 27 ms 37624 KB Output is correct
8 Correct 29 ms 38064 KB Output is correct
9 Correct 39 ms 40056 KB Output is correct
10 Correct 27 ms 37632 KB Output is correct
11 Correct 83 ms 47756 KB Output is correct
12 Correct 180 ms 58360 KB Output is correct
13 Correct 234 ms 87960 KB Output is correct
14 Correct 656 ms 100508 KB Output is correct
15 Correct 728 ms 104312 KB Output is correct
16 Correct 564 ms 90356 KB Output is correct
17 Correct 523 ms 88848 KB Output is correct
18 Correct 189 ms 56800 KB Output is correct
19 Correct 669 ms 101628 KB Output is correct
20 Correct 720 ms 104312 KB Output is correct
21 Correct 577 ms 90224 KB Output is correct
22 Correct 550 ms 90232 KB Output is correct
23 Correct 679 ms 103544 KB Output is correct
24 Correct 28 ms 37632 KB Output is correct
25 Correct 228 ms 47788 KB Output is correct
26 Correct 401 ms 58488 KB Output is correct
27 Correct 2717 ms 87968 KB Output is correct
28 Correct 2001 ms 102540 KB Output is correct
29 Correct 3540 ms 104732 KB Output is correct
30 Correct 2105 ms 91128 KB Output is correct
31 Correct 2092 ms 89208 KB Output is correct
32 Correct 255 ms 56820 KB Output is correct
33 Correct 1992 ms 101484 KB Output is correct
34 Correct 3524 ms 104568 KB Output is correct
35 Correct 2217 ms 90872 KB Output is correct
36 Correct 2105 ms 89080 KB Output is correct
37 Correct 1783 ms 103936 KB Output is correct
38 Correct 2839 ms 116976 KB Output is correct