oj.uz

Submission #87730

# Submission time Handle Problem Language Result Execution time Memory
87730 2018-12-02T08:32:39 Z JustInCase Bitaro’s Party (JOI18_bitaro) C++17
14 / 100
 2000 ms 31712 KB 
/**
Solution:
	Idea: We can precompute for each node the sqrt(n) furthest nodes with a simple dp. Then for each query
if the number of forbidden nodes is less than sqrt(n) then for sure the answer will be among the precomputed
otherwise we can simply solve it with a brutefore since the queries of this type will be less than sqrt(n).
*/
#include <bits/stdc++.h>

const int32_t MAX_N = 1e5;
const int32_t BUCKET_SIZE = 15;

bool isForbidden[MAX_N + 5];

class Graph {
private:
	struct Node {
		int32_t id;
		std::vector< std::pair< int32_t, int32_t > > dp;
		std::vector< Node* > v, rev;
	};

	int32_t cntNodes;
	Node nodes[MAX_N + 5];
	
public:
	void Init(int32_t _cntNodes) {
		cntNodes = _cntNodes;

		for(int32_t i = 1; i <= cntNodes; i++) {
			nodes[i].id = i;
		}
	}

	void AddEdge(int32_t from, int32_t to) {
		nodes[from].v.push_back(&nodes[to]);
		nodes[to].rev.push_back(&nodes[from]);
	}

	void Precompute() {
		for(int32_t i = 1; i <= cntNodes; i++) {
			std::vector< std::pair< int32_t, int32_t > > dists;
			
			dists.push_back({ 0, i });
			for(auto &x : nodes[i].v) {
				for(auto &y : x->dp) {
					dists.push_back({ y.first + 1, y.second });
				}
			}

			std::sort(dists.begin(), dists.end());
			
			for(int32_t j = dists.size() - 1; j >= 0; j--) {
				if(nodes[i].dp.size() == 0 || nodes[i].dp.back().second != dists[j].second) {
					nodes[i].dp.push_back(dists[j]);

					if(nodes[i].dp.size() == BUCKET_SIZE) {
						break;
					}
				}
			}
		}
	}

	int32_t SolveSmallK(int32_t t) {
		for(auto &x : nodes[t].dp) {
			if(!isForbidden[x.second]) {
				return x.first;
			}
		}

		return -1;
	}

	int32_t SolveBigK(int32_t t) {
		std::vector< int32_t > dp(t + 1, 0);

		int32_t ans = (isForbidden[t] ? -1 : 0);
		for(int32_t i = t - 1; i >= 1; i--) {
			bool isChanged = false;
			for(auto &x : nodes[i].rev) {
				if(x->id <= t && (x->id == t || dp[x->id] != 0)) {
					dp[i] = std::max(dp[i], dp[x->id] + 1);
					isChanged = true;
				}
			}
			
			if(isChanged && !isForbidden[i]) {
				ans = std::max(ans, dp[i]);
			}
		}

		return ans;
	}	
};

Graph g;

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int32_t n, m, q;
	std::cin >> n >> m >> q;

	g.Init(n);
	
	for(int32_t i = 0; i < m; i++) {
		int32_t u, v;
		std::cin >> u >> v;

		g.AddEdge(v, u);
	}
	
	g.Precompute();

	for(int32_t i = 0; i < q; i++) {
		int32_t t, k;
		std::cin >> t >> k;
	
		std::vector< int32_t > c(k);
		for(int32_t j = 0; j < k; j++) {
			std::cin >> c[j];

			isForbidden[c[j]] = true;
		}

		if(k >= BUCKET_SIZE) {
			std::cout << g.SolveBigK(t) << '\n';
		}
		else {
			std::cout << g.SolveSmallK(t) << '\n';
		}

		for(int32_t j = 0; j < k; j++) {
			isForbidden[c[j]] = false;
		}
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8188 KB Output is correct
2 Correct 11 ms 8188 KB Output is correct
3 Correct 10 ms 8412 KB Output is correct
4 Correct 10 ms 8412 KB Output is correct
5 Correct 13 ms 8572 KB Output is correct
6 Correct 13 ms 8572 KB Output is correct
7 Correct 13 ms 8572 KB Output is correct
8 Correct 13 ms 8600 KB Output is correct
9 Correct 13 ms 8616 KB Output is correct
10 Correct 14 ms 8620 KB Output is correct
11 Correct 14 ms 8660 KB Output is correct
12 Correct 13 ms 8660 KB Output is correct
13 Correct 13 ms 8660 KB Output is correct
14 Correct 13 ms 8660 KB Output is correct
15 Correct 13 ms 8660 KB Output is correct
16 Correct 13 ms 8660 KB Output is correct
17 Correct 13 ms 8660 KB Output is correct
18 Correct 13 ms 8660 KB Output is correct
19 Correct 13 ms 8660 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8188 KB Output is correct
2 Correct 11 ms 8188 KB Output is correct
3 Correct 10 ms 8412 KB Output is correct
4 Correct 10 ms 8412 KB Output is correct
5 Correct 13 ms 8572 KB Output is correct
6 Correct 13 ms 8572 KB Output is correct
7 Correct 13 ms 8572 KB Output is correct
8 Correct 13 ms 8600 KB Output is correct
9 Correct 13 ms 8616 KB Output is correct
10 Correct 14 ms 8620 KB Output is correct
11 Correct 14 ms 8660 KB Output is correct
12 Correct 13 ms 8660 KB Output is correct
13 Correct 13 ms 8660 KB Output is correct
14 Correct 13 ms 8660 KB Output is correct
15 Correct 13 ms 8660 KB Output is correct
16 Correct 13 ms 8660 KB Output is correct
17 Correct 13 ms 8660 KB Output is correct
18 Correct 13 ms 8660 KB Output is correct
19 Correct 13 ms 8660 KB Output is correct
20 Correct 284 ms 13284 KB Output is correct
21 Correct 278 ms 13440 KB Output is correct
22 Correct 293 ms 13440 KB Output is correct
23 Correct 273 ms 13508 KB Output is correct
24 Correct 403 ms 27520 KB Output is correct
25 Correct 428 ms 27520 KB Output is correct
26 Correct 404 ms 27520 KB Output is correct
27 Correct 392 ms 31560 KB Output is correct
28 Correct 415 ms 31712 KB Output is correct
29 Correct 385 ms 31712 KB Output is correct
30 Correct 412 ms 31712 KB Output is correct
31 Correct 420 ms 31712 KB Output is correct
32 Correct 399 ms 31712 KB Output is correct
33 Correct 361 ms 31712 KB Output is correct
34 Correct 391 ms 31712 KB Output is correct
35 Correct 350 ms 31712 KB Output is correct
36 Correct 439 ms 31712 KB Output is correct
37 Correct 391 ms 31712 KB Output is correct
38 Correct 340 ms 31712 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8188 KB Output is correct
2 Correct 11 ms 8188 KB Output is correct
3 Correct 10 ms 8412 KB Output is correct
4 Correct 10 ms 8412 KB Output is correct
5 Correct 13 ms 8572 KB Output is correct
6 Correct 13 ms 8572 KB Output is correct
7 Correct 13 ms 8572 KB Output is correct
8 Correct 13 ms 8600 KB Output is correct
9 Correct 13 ms 8616 KB Output is correct
10 Correct 14 ms 8620 KB Output is correct
11 Correct 14 ms 8660 KB Output is correct
12 Correct 13 ms 8660 KB Output is correct
13 Correct 13 ms 8660 KB Output is correct
14 Correct 13 ms 8660 KB Output is correct
15 Correct 13 ms 8660 KB Output is correct
16 Correct 13 ms 8660 KB Output is correct
17 Correct 13 ms 8660 KB Output is correct
18 Correct 13 ms 8660 KB Output is correct
19 Correct 13 ms 8660 KB Output is correct
20 Correct 284 ms 13284 KB Output is correct
21 Correct 278 ms 13440 KB Output is correct
22 Correct 293 ms 13440 KB Output is correct
23 Correct 273 ms 13508 KB Output is correct
24 Correct 403 ms 27520 KB Output is correct
25 Correct 428 ms 27520 KB Output is correct
26 Correct 404 ms 27520 KB Output is correct
27 Correct 392 ms 31560 KB Output is correct
28 Correct 415 ms 31712 KB Output is correct
29 Correct 385 ms 31712 KB Output is correct
30 Correct 412 ms 31712 KB Output is correct
31 Correct 420 ms 31712 KB Output is correct
32 Correct 399 ms 31712 KB Output is correct
33 Correct 361 ms 31712 KB Output is correct
34 Correct 391 ms 31712 KB Output is correct
35 Correct 350 ms 31712 KB Output is correct
36 Correct 439 ms 31712 KB Output is correct
37 Correct 391 ms 31712 KB Output is correct
38 Correct 340 ms 31712 KB Output is correct
39 Correct 453 ms 31712 KB Output is correct
40 Execution timed out 2044 ms 31712 KB Time limit exceeded
41 Halted 0 ms 0 KB -