oj.uz

Submission #236823

# Submission time Handle Problem Language Result Execution time Memory
236823 2020-06-03T13:45:44 Z srvlt Tropical Garden (IOI11_garden) C++14
49 / 100
 5000 ms 59128 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 = 500005;
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 used[max_N], cycle = 0, cyc[max_N], pind[max_N];

void dfs(int u, int v, int d) {
	used[v] = 1;
	for (int to : g[v]) {
		if (to == u) {
			cycle = d + 1;
		}
		if (used[to] == 0) {
			dfs(u, to, d + 1);
		}
	}
}

queue <int> q;
int dist[max_N], zero[max_N];

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

int get(int k) {
	int res = 0;
	for (int i = 0; i < n; i++) {
		if (i == p) {
			continue;
		}
		int v = zero[i];
		bfs(v);
		for (int j : adj[p]) {
			int d = dist[pind[j]];
			if (d == 0) {
				continue;
			}
			int c = cyc[pind[j]];
			if ((c == 0 && k == d) || (c > 0 && k >= d && (k - d) % c == 0)) {
				res++;
			}
		}
	}
	return res;
}

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

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]}]);
		}
	}
	memset(& used, 0, sizeof(used));
	for (int i = 0; i < cnt; i++) {
		for (int j : g[i]) {
			gr[j].pb(i);
		}
	}
	for (int i : adj[p]) {
		int v = ind[{p, i}];
		pind[i] = v;
		used[v] = 1;
		q.push(v);
		
		cycle = 0;
		memset(& used, 0, sizeof(used));
		dfs(v, v, 0);
		cyc[v] = cycle;
	}
	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 137 ms 39928 KB Output is correct
2 Correct 150 ms 40056 KB Output is correct
3 Correct 151 ms 39936 KB Output is correct
4 Correct 34 ms 39552 KB Output is correct
5 Correct 30 ms 39552 KB Output is correct
6 Correct 159 ms 40192 KB Output is correct
7 Correct 37 ms 39680 KB Output is correct
8 Correct 158 ms 39936 KB Output is correct
9 Correct 168 ms 41720 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 39928 KB Output is correct
2 Correct 150 ms 40056 KB Output is correct
3 Correct 151 ms 39936 KB Output is correct
4 Correct 34 ms 39552 KB Output is correct
5 Correct 30 ms 39552 KB Output is correct
6 Correct 159 ms 40192 KB Output is correct
7 Correct 37 ms 39680 KB Output is correct
8 Correct 158 ms 39936 KB Output is correct
9 Correct 168 ms 41720 KB Output is correct
10 Correct 44 ms 39544 KB Output is correct
11 Correct 4322 ms 49160 KB Output is correct
12 Execution timed out 5090 ms 59128 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 39928 KB Output is correct
2 Correct 150 ms 40056 KB Output is correct
3 Correct 151 ms 39936 KB Output is correct
4 Correct 34 ms 39552 KB Output is correct
5 Correct 30 ms 39552 KB Output is correct
6 Correct 159 ms 40192 KB Output is correct
7 Correct 37 ms 39680 KB Output is correct
8 Correct 158 ms 39936 KB Output is correct
9 Correct 168 ms 41720 KB Output is correct
10 Correct 44 ms 39544 KB Output is correct
11 Correct 4322 ms 49160 KB Output is correct
12 Execution timed out 5090 ms 59128 KB Time limit exceeded
13 Halted 0 ms 0 KB -