oj.uz

Submission #87736

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

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) {
					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]);
					}
					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]);
			}
			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) {
				auto aux = x->dp;
				for(auto &y : aux) {
					y.first++;
				}
				nodes[i].dp = Merge(nodes[i].dp, aux);
			}
		}
	}

	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 10 ms 8312 KB Output is correct
2 Correct 10 ms 8312 KB Output is correct
3 Correct 11 ms 8328 KB Output is correct
4 Correct 10 ms 8328 KB Output is correct
5 Correct 15 ms 8664 KB Output is correct
6 Correct 15 ms 8712 KB Output is correct
7 Correct 15 ms 8712 KB Output is correct
8 Correct 14 ms 8856 KB Output is correct
9 Correct 14 ms 8968 KB Output is correct
10 Correct 14 ms 8996 KB Output is correct
11 Correct 15 ms 8996 KB Output is correct
12 Correct 12 ms 8996 KB Output is correct
13 Correct 13 ms 8996 KB Output is correct
14 Correct 12 ms 8996 KB Output is correct
15 Correct 14 ms 8996 KB Output is correct
16 Correct 14 ms 8996 KB Output is correct
17 Correct 13 ms 8996 KB Output is correct
18 Correct 14 ms 8996 KB Output is correct
19 Correct 15 ms 8996 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8312 KB Output is correct
2 Correct 10 ms 8312 KB Output is correct
3 Correct 11 ms 8328 KB Output is correct
4 Correct 10 ms 8328 KB Output is correct
5 Correct 15 ms 8664 KB Output is correct
6 Correct 15 ms 8712 KB Output is correct
7 Correct 15 ms 8712 KB Output is correct
8 Correct 14 ms 8856 KB Output is correct
9 Correct 14 ms 8968 KB Output is correct
10 Correct 14 ms 8996 KB Output is correct
11 Correct 15 ms 8996 KB Output is correct
12 Correct 12 ms 8996 KB Output is correct
13 Correct 13 ms 8996 KB Output is correct
14 Correct 12 ms 8996 KB Output is correct
15 Correct 14 ms 8996 KB Output is correct
16 Correct 14 ms 8996 KB Output is correct
17 Correct 13 ms 8996 KB Output is correct
18 Correct 14 ms 8996 KB Output is correct
19 Correct 15 ms 8996 KB Output is correct
20 Correct 238 ms 13372 KB Output is correct
21 Correct 236 ms 13372 KB Output is correct
22 Correct 247 ms 13528 KB Output is correct
23 Correct 245 ms 13528 KB Output is correct
24 Correct 540 ms 56776 KB Output is correct
25 Correct 549 ms 56956 KB Output is correct
26 Correct 568 ms 56956 KB Output is correct
27 Correct 530 ms 69204 KB Output is correct
28 Correct 565 ms 69300 KB Output is correct
29 Correct 526 ms 69300 KB Output is correct
30 Correct 543 ms 69300 KB Output is correct
31 Correct 530 ms 69300 KB Output is correct
32 Correct 518 ms 69300 KB Output is correct
33 Correct 512 ms 69300 KB Output is correct
34 Correct 488 ms 69300 KB Output is correct
35 Correct 494 ms 69300 KB Output is correct
36 Correct 459 ms 69300 KB Output is correct
37 Correct 458 ms 69300 KB Output is correct
38 Correct 510 ms 69300 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8312 KB Output is correct
2 Correct 10 ms 8312 KB Output is correct
3 Correct 11 ms 8328 KB Output is correct
4 Correct 10 ms 8328 KB Output is correct
5 Correct 15 ms 8664 KB Output is correct
6 Correct 15 ms 8712 KB Output is correct
7 Correct 15 ms 8712 KB Output is correct
8 Correct 14 ms 8856 KB Output is correct
9 Correct 14 ms 8968 KB Output is correct
10 Correct 14 ms 8996 KB Output is correct
11 Correct 15 ms 8996 KB Output is correct
12 Correct 12 ms 8996 KB Output is correct
13 Correct 13 ms 8996 KB Output is correct
14 Correct 12 ms 8996 KB Output is correct
15 Correct 14 ms 8996 KB Output is correct
16 Correct 14 ms 8996 KB Output is correct
17 Correct 13 ms 8996 KB Output is correct
18 Correct 14 ms 8996 KB Output is correct
19 Correct 15 ms 8996 KB Output is correct
20 Correct 238 ms 13372 KB Output is correct
21 Correct 236 ms 13372 KB Output is correct
22 Correct 247 ms 13528 KB Output is correct
23 Correct 245 ms 13528 KB Output is correct
24 Correct 540 ms 56776 KB Output is correct
25 Correct 549 ms 56956 KB Output is correct
26 Correct 568 ms 56956 KB Output is correct
27 Correct 530 ms 69204 KB Output is correct
28 Correct 565 ms 69300 KB Output is correct
29 Correct 526 ms 69300 KB Output is correct
30 Correct 543 ms 69300 KB Output is correct
31 Correct 530 ms 69300 KB Output is correct
32 Correct 518 ms 69300 KB Output is correct
33 Correct 512 ms 69300 KB Output is correct
34 Correct 488 ms 69300 KB Output is correct
35 Correct 494 ms 69300 KB Output is correct
36 Correct 459 ms 69300 KB Output is correct
37 Correct 458 ms 69300 KB Output is correct
38 Correct 510 ms 69300 KB Output is correct
39 Correct 702 ms 69300 KB Output is correct
40 Correct 647 ms 69300 KB Output is correct
41 Execution timed out 2056 ms 69300 KB Time limit exceeded
42 Halted 0 ms 0 KB -