oj.uz

Submission #202091

# Submission time Handle Problem Language Result Execution time Memory
202091 2020-02-13T19:31:14 Z Fischer Tropical Garden (IOI11_garden) C++14
100 / 100
 213 ms 25648 KB 
#include <bits/stdc++.h>
#include "gardenlib.h"
using namespace std;

int _left(int x) {
	return x<<1;
}

int _right(int x) {
	return x<<1|1;
}

bool is_left(int x) {
	return _left(x/2) == x;
}

vector<int> make_functional_graph(int n, int E[][2], int m) {
	vector<int> F(2 * n);
	vector<vector<int>> best(n);
	for (int i = 0; i < m; ++i) {
		int u = E[i][0], v = E[i][1];
		best[u].emplace_back(v);
		best[v].emplace_back(u);
	}
	for (int i = 0; i < n; ++i) {
		if (best[i].size() == 1) {
			best[i].emplace_back(best[i][0]);
		}
	}
	for (int i = 0; i < n; ++i) {
		int a = best[i][0], b = best[i][1];
		F[_left(i)] = best[a][0] == i ? (best[a][0] == best[a][1] ? _left(a) : _right(a)) : _left(a);
		F[_right(i)] = best[b][0] == i ? (best[b][0] == best[b][1] ? _left(b) : _right(b)) : _left(b);
	}
	return F;
}

vector<vector<int>> make_reverse_functional(vector<int> F) {
	vector<vector<int>> Gt(F.size());
	for (int i = 0; i < F.size(); ++i) {	
		Gt[F[i]].emplace_back(i);
	}
	return Gt;
}

const int inf = 1e9;
vector<int> bfs(vector<vector<int>> G, int src) {
	vector<int> dis(G.size(), inf);
	dis[src] = 0;
	queue<int> Q;
	Q.push(src);
	while (not Q.empty()) {
		int q = Q.front(); Q.pop();
		for (int v : G[q]) {
			if (dis[q] + 1 < dis[v]) {
				dis[v] = dis[q] + 1;
				Q.push(v);
			}
		}
	}
	return dis;
}

vector<int> get_cycle_from_functional(vector<int> F, int x) {
	vector<int> cycle;
	vector<bool> vis(F.size());
	while (not vis[x]) {
		vis[x] = 1;
		x = F[x];
	}
	int t = x;
	do {
		cycle.emplace_back(x);
		x = F[x];
	} while (x != t);
	return cycle;
}

bool is_in(int t, vector<int> v) {
	for (int e : v) {
		if (e == t) {
			return 1;
		}
	}
	return 0;
}

vector<int> solve(vector<int> F, int x) {
	auto dis = bfs(make_reverse_functional(F), x);
	auto cycle = get_cycle_from_functional(F, x);
	int cycle_len = cycle.size();
	int n = F.size();
	vector<int> ans(n);
	if (is_in(x, cycle)) {
		for (int i = 0; i < n; ++i) {
			if (dis[i] >= inf) continue;
			if (not is_left(i)) continue; 
			ans[dis[i]] += 1;
		}
		for (int i = 0; i + cycle_len < n; ++i) {
			ans[i + cycle_len] += ans[i];
		}
	} else {
		for (int i = 0; i < n; ++i) {
			if (dis[i] >= inf) continue;
			if (not is_left(i)) continue;
			ans[dis[i]] += 1;
		}
	}
	return ans;
}

void count_routes(int n, int m, int p, int R[][2], int q, int Q[]) {
	auto G = make_functional_graph(n, R, m);
	auto ans1 = solve(G, _left(p));
	auto ans2 = solve(G, _right(p));
	auto cycle_l = get_cycle_from_functional(G, _left(p));
	auto cycle_r = get_cycle_from_functional(G, _right(p));
	bool o1 = is_in(_left(p), cycle_l);
	bool o2 = is_in(_right(p), cycle_r);
	int c_l_len = cycle_l.size();
	int c_r_len = cycle_r.size();
	for (int i = 0; i < q; ++i) {
		int temp = 0;
		if (o1) {
			if (Q[i] < 2*n) temp += ans1[Q[i]];
			else temp += ans1[Q[i] - ((Q[i] - 2 * n) / c_l_len + 1) * c_l_len];
		} else {
			temp += (Q[i] >= 2*n ? 0 : ans1[Q[i]]);
		}
		//if (G[_left(p)] != G[_right(p)]) {
		if (o2) {
			if (Q[i] < 2*n) temp += ans2[Q[i]];
			else temp += ans2[Q[i] - ((Q[i] - 2 * n) / c_r_len + 1) * c_r_len];
		} else {
			temp += (Q[i] >= 2*n ? 0 : ans2[Q[i]]);
		}
		//}
		answer(temp);
	}
}

Compilation message

garden.cpp: In function 'std::vector<std::vector<int> > make_reverse_functional(std::vector<int>)':
garden.cpp:40:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < F.size(); ++i) { 
                  ~~^~~~~~~~~~

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 508 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 8 ms 632 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 508 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 8 ms 632 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 21 ms 3648 KB Output is correct
12 Correct 46 ms 6052 KB Output is correct
13 Correct 74 ms 14668 KB Output is correct
14 Correct 198 ms 19276 KB Output is correct
15 Correct 206 ms 19664 KB Output is correct
16 Correct 141 ms 14148 KB Output is correct
17 Correct 163 ms 12516 KB Output is correct
18 Correct 44 ms 5920 KB Output is correct
19 Correct 172 ms 19272 KB Output is correct
20 Correct 210 ms 19688 KB Output is correct
21 Correct 149 ms 14148 KB Output is correct
22 Correct 128 ms 12516 KB Output is correct
23 Correct 184 ms 21128 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 508 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 8 ms 632 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 21 ms 3648 KB Output is correct
12 Correct 46 ms 6052 KB Output is correct
13 Correct 74 ms 14668 KB Output is correct
14 Correct 198 ms 19276 KB Output is correct
15 Correct 206 ms 19664 KB Output is correct
16 Correct 141 ms 14148 KB Output is correct
17 Correct 163 ms 12516 KB Output is correct
18 Correct 44 ms 5920 KB Output is correct
19 Correct 172 ms 19272 KB Output is correct
20 Correct 210 ms 19688 KB Output is correct
21 Correct 149 ms 14148 KB Output is correct
22 Correct 128 ms 12516 KB Output is correct
23 Correct 184 ms 21128 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 21 ms 3652 KB Output is correct
26 Correct 42 ms 5920 KB Output is correct
27 Correct 77 ms 14760 KB Output is correct
28 Correct 179 ms 19432 KB Output is correct
29 Correct 213 ms 19776 KB Output is correct
30 Correct 145 ms 14276 KB Output is correct
31 Correct 124 ms 12516 KB Output is correct
32 Correct 44 ms 5924 KB Output is correct
33 Correct 172 ms 19328 KB Output is correct
34 Correct 198 ms 19688 KB Output is correct
35 Correct 141 ms 14276 KB Output is correct
36 Correct 126 ms 12516 KB Output is correct
37 Correct 176 ms 21172 KB Output is correct
38 Correct 150 ms 25648 KB Output is correct