oj.uz

Submission #87750

# Submission time Handle Problem Language Result Execution time Memory
87750 2018-12-02T09:24:31 Z JustInCase Bitaro’s Party (JOI18_bitaro) C++17
0 / 100
 22 ms 9520 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;
const int32_t INF = 2e9;

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

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

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

		for(int32_t i = 1; i <= t; i++) {
			if(isForbidden[i]) {
				dp[i] = -INF;
			}
			else {
				dp[i] = 0;
			}

			for(auto &x : nodes[i].v) {
				dp[i] = std::max(dp[i], dp[x->id] + 1);
			}
		}

		return dp[t];
	}	
};

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:21:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while((ind1 < v1.size() || ind2 < v2.size()) && ans.size() < BUCKET_SIZE) {
         ~~~~~^~~~~~~~~~~
bitaro.cpp:21:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while((ind1 < v1.size() || ind2 < v2.size()) && ans.size() < BUCKET_SIZE) {
                             ~~~~~^~~~~~~~~~~
bitaro.cpp:22:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ind1 < v1.size()) {
      ~~~~~^~~~~~~~~~~
bitaro.cpp:23:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ind2 < v2.size()) {
       ~~~~~^~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5880 KB Output is correct
2 Correct 7 ms 5988 KB Output is correct
3 Correct 7 ms 6000 KB Output is correct
4 Correct 7 ms 6000 KB Output is correct
5 Correct 11 ms 6500 KB Output is correct
6 Correct 11 ms 6500 KB Output is correct
7 Correct 10 ms 6500 KB Output is correct
8 Correct 20 ms 9520 KB Output is correct
9 Correct 22 ms 9520 KB Output is correct
10 Correct 20 ms 9520 KB Output is correct
11 Correct 20 ms 9520 KB Output is correct
12 Correct 14 ms 9520 KB Output is correct
13 Incorrect 18 ms 9520 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5880 KB Output is correct
2 Correct 7 ms 5988 KB Output is correct
3 Correct 7 ms 6000 KB Output is correct
4 Correct 7 ms 6000 KB Output is correct
5 Correct 11 ms 6500 KB Output is correct
6 Correct 11 ms 6500 KB Output is correct
7 Correct 10 ms 6500 KB Output is correct
8 Correct 20 ms 9520 KB Output is correct
9 Correct 22 ms 9520 KB Output is correct
10 Correct 20 ms 9520 KB Output is correct
11 Correct 20 ms 9520 KB Output is correct
12 Correct 14 ms 9520 KB Output is correct
13 Incorrect 18 ms 9520 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5880 KB Output is correct
2 Correct 7 ms 5988 KB Output is correct
3 Correct 7 ms 6000 KB Output is correct
4 Correct 7 ms 6000 KB Output is correct
5 Correct 11 ms 6500 KB Output is correct
6 Correct 11 ms 6500 KB Output is correct
7 Correct 10 ms 6500 KB Output is correct
8 Correct 20 ms 9520 KB Output is correct
9 Correct 22 ms 9520 KB Output is correct
10 Correct 20 ms 9520 KB Output is correct
11 Correct 20 ms 9520 KB Output is correct
12 Correct 14 ms 9520 KB Output is correct
13 Incorrect 18 ms 9520 KB Output isn't correct
14 Halted 0 ms 0 KB -