oj.uz

Submission #66978

# Submission time Handle Problem Language Result Execution time Memory
66978 2018-08-13T06:06:33 Z szawinis Bitaro’s Party (JOI18_bitaro) C++17
0 / 100
 20 ms 8664 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+1, INF = 1e9+1;

int n, m, q, bsz = 300;
vector<int> g[N];
vector<pair<int,int> > dp[N];
bool blocked[N];
int f[N];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> q;
	for(int i = 0, s, e; i < m; i++) {
		cin >> s >> e;
		--s, --e;
		g[e].push_back(s);
	}
	dp[0].emplace_back(0, 0);
	for(int i = 1; i < n; i++) {
		dp[i].emplace_back(0, i);
		for(int j: g[i]) for(auto x: dp[j]) dp[i].emplace_back(x.first + 1, x.second);
		nth_element(dp[i].begin(), dp[i].begin() + min(bsz, (int) dp[i].size()), dp[i].end());
		dp[i].resize(min(bsz, (int) dp[i].size()));
	}
	while(q--) {
		int targ, Y;
		cin >> targ >> Y;
		--targ;
		vector<int> C(Y);
		for(int i = 0; i < Y; i++) {
			cin >> C[i];
			--C[i];
			blocked[C[i]] = true;
		}
		int res = -INF;
		if(Y < bsz) {
			for(auto p: dp[targ]) if(!blocked[p.second]) res = max(p.first, res);
		} else {
			fill(f, f+targ+1, 0);
			for(int i: C) f[i] = -INF;
			for(int i = 0; i <= targ; i++) if(f[i] != -INF) for(int j: g[i]) {
				f[i] = max(f[j] + 1, f[i]);
			}
		}
		if(res == -INF) cout << -1;
		else cout << res;
		cout << '\n';
		for(int i = 0; i < Y; i++) blocked[C[i]] = false;
	}
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4988 KB Output is correct
2 Correct 7 ms 5108 KB Output is correct
3 Correct 7 ms 5184 KB Output is correct
4 Correct 8 ms 5260 KB Output is correct
5 Incorrect 20 ms 8664 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4988 KB Output is correct
2 Correct 7 ms 5108 KB Output is correct
3 Correct 7 ms 5184 KB Output is correct
4 Correct 8 ms 5260 KB Output is correct
5 Incorrect 20 ms 8664 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4988 KB Output is correct
2 Correct 7 ms 5108 KB Output is correct
3 Correct 7 ms 5184 KB Output is correct
4 Correct 8 ms 5260 KB Output is correct
5 Incorrect 20 ms 8664 KB Output isn't correct
6 Halted 0 ms 0 KB -