oj.uz

Submission #87746

# Submission time Handle Problem Language Result Execution time Memory
87746 2018-12-02T09:13:47 Z JustInCase Bitaro’s Party (JOI18_bitaro) C++17
14 / 100
 2000 ms 419436 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 = 300;

bool isInVector[MAX_N + 5];
bool isForbidden[MAX_N + 5];

std::vector< std::pair< int32_t, int32_t > > Merge(const std::vector< std::pair< int32_t, int32_t> > &v1, 
		const std::vector< std::pair< int32_t, int32_t > > &v2) {
	std::vector< std::pair< int32_t, int32_t > > ans;

	int32_t ind1 = 0, ind2 = 0;
	while((ind1 < v1.size() || ind2 < v2.size()) && ans.size() < BUCKET_SIZE) {
		if(ind1 < v1.size()) {
			if(ind2 < v2.size()) {
				if(v1[ind1].first >= v2[ind2].first + 1) {
					if(!isInVector[v1[ind1].second]) {
						isInVector[v1[ind1].second] = true;
						ans.push_back(v1[ind1]);
					}
					ind1++;
				}
				else {
					if(!isInVector[v2[ind2].second]) {
						isInVector[v2[ind2].second] = true;
						ans.push_back({ v2[ind2].first + 1, v2[ind2].second });
					}
					ind2++;
				}
			}
			else {
				if(!isInVector[v1[ind1].second]) {
					isInVector[v1[ind1].second] = true;
					ans.push_back(v1[ind1]);
				}
				ind1++;
			}
		}
		else {
			if(!isInVector[v2[ind2].second]) {
				isInVector[v2[ind2].second] = true;
				ans.push_back({ v2[ind2].first + 1, v2[ind2].second });
			}
			ind2++;
		}
	}

	for(auto &x : ans) {
		isInVector[x.second] = false;
	}

	return ans;
}

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;
			
			nodes[i].dp.push_back({ 0, i });
			for(auto &x : nodes[i].v) {
				nodes[i].dp = Merge(nodes[i].dp, x->dp);
			}
		}
	}

	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;
		}
	}
}

Compilation message

bitaro.cpp: In function 'std::vector<std::pair<int, int> > Merge(const std::vector<std::pair<int, int> >&, const std::vector<std::pair<int, int> >&)':
bitaro.cpp:20:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while((ind1 < v1.size() || ind2 < v2.size()) && ans.size() < BUCKET_SIZE) {
         ~~~~~^~~~~~~~~~~
bitaro.cpp:20:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while((ind1 < v1.size() || ind2 < v2.size()) && ans.size() < BUCKET_SIZE) {
                             ~~~~~^~~~~~~~~~~
bitaro.cpp:21:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ind1 < v1.size()) {
      ~~~~~^~~~~~~~~~~
bitaro.cpp:22:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ind2 < v2.size()) {
       ~~~~~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 10 ms 8316 KB Output is correct
3 Correct 11 ms 8316 KB Output is correct
4 Correct 10 ms 8332 KB Output is correct
5 Correct 13 ms 8848 KB Output is correct
6 Correct 13 ms 8896 KB Output is correct
7 Correct 13 ms 9020 KB Output is correct
8 Correct 23 ms 11856 KB Output is correct
9 Correct 25 ms 11856 KB Output is correct
10 Correct 22 ms 11868 KB Output is correct
11 Correct 25 ms 11868 KB Output is correct
12 Correct 17 ms 11868 KB Output is correct
13 Correct 25 ms 11868 KB Output is correct
14 Correct 23 ms 11868 KB Output is correct
15 Correct 17 ms 11868 KB Output is correct
16 Correct 17 ms 11868 KB Output is correct
17 Correct 20 ms 11868 KB Output is correct
18 Correct 16 ms 11868 KB Output is correct
19 Correct 20 ms 11868 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 10 ms 8316 KB Output is correct
3 Correct 11 ms 8316 KB Output is correct
4 Correct 10 ms 8332 KB Output is correct
5 Correct 13 ms 8848 KB Output is correct
6 Correct 13 ms 8896 KB Output is correct
7 Correct 13 ms 9020 KB Output is correct
8 Correct 23 ms 11856 KB Output is correct
9 Correct 25 ms 11856 KB Output is correct
10 Correct 22 ms 11868 KB Output is correct
11 Correct 25 ms 11868 KB Output is correct
12 Correct 17 ms 11868 KB Output is correct
13 Correct 25 ms 11868 KB Output is correct
14 Correct 23 ms 11868 KB Output is correct
15 Correct 17 ms 11868 KB Output is correct
16 Correct 17 ms 11868 KB Output is correct
17 Correct 20 ms 11868 KB Output is correct
18 Correct 16 ms 11868 KB Output is correct
19 Correct 20 ms 11868 KB Output is correct
20 Correct 715 ms 16168 KB Output is correct
21 Correct 641 ms 16332 KB Output is correct
22 Correct 729 ms 16332 KB Output is correct
23 Correct 755 ms 16392 KB Output is correct
24 Correct 1476 ms 259296 KB Output is correct
25 Correct 1534 ms 270832 KB Output is correct
26 Correct 1434 ms 270832 KB Output is correct
27 Correct 1465 ms 419180 KB Output is correct
28 Correct 1449 ms 419308 KB Output is correct
29 Correct 1491 ms 419436 KB Output is correct
30 Correct 1566 ms 419436 KB Output is correct
31 Correct 1781 ms 419436 KB Output is correct
32 Correct 1473 ms 419436 KB Output is correct
33 Correct 1131 ms 419436 KB Output is correct
34 Correct 1051 ms 419436 KB Output is correct
35 Correct 1173 ms 419436 KB Output is correct
36 Correct 1439 ms 419436 KB Output is correct
37 Correct 1464 ms 419436 KB Output is correct
38 Correct 1488 ms 419436 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 10 ms 8316 KB Output is correct
3 Correct 11 ms 8316 KB Output is correct
4 Correct 10 ms 8332 KB Output is correct
5 Correct 13 ms 8848 KB Output is correct
6 Correct 13 ms 8896 KB Output is correct
7 Correct 13 ms 9020 KB Output is correct
8 Correct 23 ms 11856 KB Output is correct
9 Correct 25 ms 11856 KB Output is correct
10 Correct 22 ms 11868 KB Output is correct
11 Correct 25 ms 11868 KB Output is correct
12 Correct 17 ms 11868 KB Output is correct
13 Correct 25 ms 11868 KB Output is correct
14 Correct 23 ms 11868 KB Output is correct
15 Correct 17 ms 11868 KB Output is correct
16 Correct 17 ms 11868 KB Output is correct
17 Correct 20 ms 11868 KB Output is correct
18 Correct 16 ms 11868 KB Output is correct
19 Correct 20 ms 11868 KB Output is correct
20 Correct 715 ms 16168 KB Output is correct
21 Correct 641 ms 16332 KB Output is correct
22 Correct 729 ms 16332 KB Output is correct
23 Correct 755 ms 16392 KB Output is correct
24 Correct 1476 ms 259296 KB Output is correct
25 Correct 1534 ms 270832 KB Output is correct
26 Correct 1434 ms 270832 KB Output is correct
27 Correct 1465 ms 419180 KB Output is correct
28 Correct 1449 ms 419308 KB Output is correct
29 Correct 1491 ms 419436 KB Output is correct
30 Correct 1566 ms 419436 KB Output is correct
31 Correct 1781 ms 419436 KB Output is correct
32 Correct 1473 ms 419436 KB Output is correct
33 Correct 1131 ms 419436 KB Output is correct
34 Correct 1051 ms 419436 KB Output is correct
35 Correct 1173 ms 419436 KB Output is correct
36 Correct 1439 ms 419436 KB Output is correct
37 Correct 1464 ms 419436 KB Output is correct
38 Correct 1488 ms 419436 KB Output is correct
39 Correct 1712 ms 419436 KB Output is correct
40 Correct 1634 ms 419436 KB Output is correct
41 Correct 1677 ms 419436 KB Output is correct
42 Execution timed out 2093 ms 419436 KB Time limit exceeded
43 Halted 0 ms 0 KB -