oj.uz

Submission #87682

# Submission time Handle Problem Language Result Execution time Memory
87682 2018-12-01T21:14:07 Z JustInCase Bitaro’s Party (JOI18_bitaro) C++17
7 / 100
 2000 ms 17092 KB 
#include <bits/stdc++.h>

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

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 11 ms 8184 KB Output is correct
2 Correct 10 ms 8184 KB Output is correct
3 Correct 9 ms 8200 KB Output is correct
4 Correct 9 ms 8244 KB Output is correct
5 Correct 24 ms 9812 KB Output is correct
6 Correct 23 ms 9812 KB Output is correct
7 Correct 24 ms 9812 KB Output is correct
8 Correct 49 ms 12440 KB Output is correct
9 Correct 48 ms 12524 KB Output is correct
10 Correct 47 ms 12524 KB Output is correct
11 Correct 44 ms 12524 KB Output is correct
12 Correct 29 ms 12524 KB Output is correct
13 Correct 46 ms 12524 KB Output is correct
14 Correct 39 ms 12524 KB Output is correct
15 Correct 26 ms 12524 KB Output is correct
16 Correct 36 ms 12524 KB Output is correct
17 Correct 43 ms 12524 KB Output is correct
18 Correct 28 ms 12524 KB Output is correct
19 Correct 45 ms 12524 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8184 KB Output is correct
2 Correct 10 ms 8184 KB Output is correct
3 Correct 9 ms 8200 KB Output is correct
4 Correct 9 ms 8244 KB Output is correct
5 Correct 24 ms 9812 KB Output is correct
6 Correct 23 ms 9812 KB Output is correct
7 Correct 24 ms 9812 KB Output is correct
8 Correct 49 ms 12440 KB Output is correct
9 Correct 48 ms 12524 KB Output is correct
10 Correct 47 ms 12524 KB Output is correct
11 Correct 44 ms 12524 KB Output is correct
12 Correct 29 ms 12524 KB Output is correct
13 Correct 46 ms 12524 KB Output is correct
14 Correct 39 ms 12524 KB Output is correct
15 Correct 26 ms 12524 KB Output is correct
16 Correct 36 ms 12524 KB Output is correct
17 Correct 43 ms 12524 KB Output is correct
18 Correct 28 ms 12524 KB Output is correct
19 Correct 45 ms 12524 KB Output is correct
20 Execution timed out 2029 ms 17092 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8184 KB Output is correct
2 Correct 10 ms 8184 KB Output is correct
3 Correct 9 ms 8200 KB Output is correct
4 Correct 9 ms 8244 KB Output is correct
5 Correct 24 ms 9812 KB Output is correct
6 Correct 23 ms 9812 KB Output is correct
7 Correct 24 ms 9812 KB Output is correct
8 Correct 49 ms 12440 KB Output is correct
9 Correct 48 ms 12524 KB Output is correct
10 Correct 47 ms 12524 KB Output is correct
11 Correct 44 ms 12524 KB Output is correct
12 Correct 29 ms 12524 KB Output is correct
13 Correct 46 ms 12524 KB Output is correct
14 Correct 39 ms 12524 KB Output is correct
15 Correct 26 ms 12524 KB Output is correct
16 Correct 36 ms 12524 KB Output is correct
17 Correct 43 ms 12524 KB Output is correct
18 Correct 28 ms 12524 KB Output is correct
19 Correct 45 ms 12524 KB Output is correct
20 Execution timed out 2029 ms 17092 KB Time limit exceeded
21 Halted 0 ms 0 KB -