oj.uz

답안 #87679

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
87679 2018-12-01T20:45:14 Z JustInCase Bitaro’s Party (JOI18_bitaro) C++17
0 / 100
 49 ms 12488 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 {
		bool isVisited;
		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--) {
			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);
				}
			}
			
			if(!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 i = 0; i < k; i++) {
			std::cin >> c[i];

			isForbidden[c[i]] = true;
		}

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

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

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct
3 Correct 9 ms 8256 KB Output is correct
4 Correct 9 ms 8464 KB Output is correct
5 Correct 24 ms 9808 KB Output is correct
6 Correct 21 ms 9808 KB Output is correct
7 Correct 24 ms 9808 KB Output is correct
8 Correct 49 ms 12488 KB Output is correct
9 Correct 45 ms 12488 KB Output is correct
10 Correct 47 ms 12488 KB Output is correct
11 Correct 43 ms 12488 KB Output is correct
12 Correct 29 ms 12488 KB Output is correct
13 Correct 43 ms 12488 KB Output is correct
14 Incorrect 36 ms 12488 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct
3 Correct 9 ms 8256 KB Output is correct
4 Correct 9 ms 8464 KB Output is correct
5 Correct 24 ms 9808 KB Output is correct
6 Correct 21 ms 9808 KB Output is correct
7 Correct 24 ms 9808 KB Output is correct
8 Correct 49 ms 12488 KB Output is correct
9 Correct 45 ms 12488 KB Output is correct
10 Correct 47 ms 12488 KB Output is correct
11 Correct 43 ms 12488 KB Output is correct
12 Correct 29 ms 12488 KB Output is correct
13 Correct 43 ms 12488 KB Output is correct
14 Incorrect 36 ms 12488 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct
3 Correct 9 ms 8256 KB Output is correct
4 Correct 9 ms 8464 KB Output is correct
5 Correct 24 ms 9808 KB Output is correct
6 Correct 21 ms 9808 KB Output is correct
7 Correct 24 ms 9808 KB Output is correct
8 Correct 49 ms 12488 KB Output is correct
9 Correct 45 ms 12488 KB Output is correct
10 Correct 47 ms 12488 KB Output is correct
11 Correct 43 ms 12488 KB Output is correct
12 Correct 29 ms 12488 KB Output is correct
13 Correct 43 ms 12488 KB Output is correct
14 Incorrect 36 ms 12488 KB Output isn't correct
15 Halted 0 ms 0 KB -