oj.uz

Submission #236869

# Submission time Handle Problem Language Result Execution time Memory
236869 2020-06-03T15:28:45 Z srvlt Tropical Garden (IOI11_garden) C++14
100 / 100
 3550 ms 111436 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#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 = 450007;
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;
			}
			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);
		}
	}
	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 28 ms 34304 KB Output is correct
2 Correct 29 ms 34304 KB Output is correct
3 Correct 29 ms 34304 KB Output is correct
4 Correct 28 ms 33912 KB Output is correct
5 Correct 26 ms 33920 KB Output is correct
6 Correct 29 ms 34688 KB Output is correct
7 Correct 28 ms 33912 KB Output is correct
8 Correct 28 ms 34304 KB Output is correct
9 Correct 36 ms 36224 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 34304 KB Output is correct
2 Correct 29 ms 34304 KB Output is correct
3 Correct 29 ms 34304 KB Output is correct
4 Correct 28 ms 33912 KB Output is correct
5 Correct 26 ms 33920 KB Output is correct
6 Correct 29 ms 34688 KB Output is correct
7 Correct 28 ms 33912 KB Output is correct
8 Correct 28 ms 34304 KB Output is correct
9 Correct 36 ms 36224 KB Output is correct
10 Correct 26 ms 33920 KB Output is correct
11 Correct 90 ms 44024 KB Output is correct
12 Correct 182 ms 54648 KB Output is correct
13 Correct 244 ms 83704 KB Output is correct
14 Correct 658 ms 96248 KB Output is correct
15 Correct 692 ms 99960 KB Output is correct
16 Correct 553 ms 86008 KB Output is correct
17 Correct 520 ms 84472 KB Output is correct
18 Correct 193 ms 53112 KB Output is correct
19 Correct 634 ms 97444 KB Output is correct
20 Correct 712 ms 100020 KB Output is correct
21 Correct 566 ms 85752 KB Output is correct
22 Correct 539 ms 85856 KB Output is correct
23 Correct 671 ms 99416 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 34304 KB Output is correct
2 Correct 29 ms 34304 KB Output is correct
3 Correct 29 ms 34304 KB Output is correct
4 Correct 28 ms 33912 KB Output is correct
5 Correct 26 ms 33920 KB Output is correct
6 Correct 29 ms 34688 KB Output is correct
7 Correct 28 ms 33912 KB Output is correct
8 Correct 28 ms 34304 KB Output is correct
9 Correct 36 ms 36224 KB Output is correct
10 Correct 26 ms 33920 KB Output is correct
11 Correct 90 ms 44024 KB Output is correct
12 Correct 182 ms 54648 KB Output is correct
13 Correct 244 ms 83704 KB Output is correct
14 Correct 658 ms 96248 KB Output is correct
15 Correct 692 ms 99960 KB Output is correct
16 Correct 553 ms 86008 KB Output is correct
17 Correct 520 ms 84472 KB Output is correct
18 Correct 193 ms 53112 KB Output is correct
19 Correct 634 ms 97444 KB Output is correct
20 Correct 712 ms 100020 KB Output is correct
21 Correct 566 ms 85752 KB Output is correct
22 Correct 539 ms 85856 KB Output is correct
23 Correct 671 ms 99416 KB Output is correct
24 Correct 27 ms 33920 KB Output is correct
25 Correct 201 ms 44152 KB Output is correct
26 Correct 354 ms 54776 KB Output is correct
27 Correct 2710 ms 83820 KB Output is correct
28 Correct 1758 ms 97784 KB Output is correct
29 Correct 3495 ms 99968 KB Output is correct
30 Correct 2094 ms 86136 KB Output is correct
31 Correct 2040 ms 84472 KB Output is correct
32 Correct 256 ms 52732 KB Output is correct
33 Correct 1795 ms 95996 KB Output is correct
34 Correct 3550 ms 99192 KB Output is correct
35 Correct 2249 ms 85752 KB Output is correct
36 Correct 2028 ms 83832 KB Output is correct
37 Correct 1522 ms 98424 KB Output is correct
38 Correct 2686 ms 111436 KB Output is correct