oj.uz

Submission #94457

# Submission time Handle Problem Language Result Execution time Memory
94457 2019-01-18T17:08:25 Z aminra Bitaro’s Party (JOI18_bitaro) C++14
14 / 100
 1299 ms 257936 KB 
//Smaug never desolated!!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = (int)100007;
const int block = 320;
const int infint = (int)1e8 + 3;
const int MOD = (int)1e9 + 7;
const ll inf = (ll)1e18;
int n, m, q, bad[MAXN], dp[MAXN], input[MAXN], prv[MAXN];
pair<int, int> DP[MAXN][block], tmp[block];
vector<int> in[MAXN];
bool cmp(pair<int, int> a, pair<int, int> b)
{
	return a.second > b.second;
}
inline void merge(int a, int b)
{
	int sz = 0;
	vector<int> used;
	for (int i = 0; i < block; i++)
		tmp[i] = {-1, -1};
	int ptr1 = 0, ptr2 = 0;
	while(sz < block && (ptr1 < block || ptr2 < block))
	{
		while(ptr1 < block && DP[a][ptr1].first != -1 && prv[DP[a][ptr1].first])
			ptr1++;
		while(ptr2 < block && DP[b][ptr2].first != -1 && prv[DP[b][ptr2].first])
			ptr2++;
		pair<int, int> B = {-1, -1};
		if(ptr2 != block && DP[b][ptr2].first != -1)
			B = DP[b][ptr2], B.second++;
		if(ptr1 != block && (ptr2 == block || cmp(DP[a][ptr1], B)))
		{
			tmp[sz] = DP[a][ptr1], ptr1++, sz++;
			int idx = DP[a][ptr1].first;
			if(idx != -1)
				prv[idx] = 1, used.push_back(idx);
		}
		else
		{
			tmp[sz] = B, ptr2++, sz++;
			int idx = B.first;
			if(idx != -1)
				prv[idx] = 1, used.push_back(idx);
		}
	}
	for (int i = 0; i < block; i++)
		DP[a][i] = tmp[i];
	for (auto u : used)
		prv[u] = 0;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> q;
	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		in[v].push_back(u);
	}
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < block; j++)
			DP[i][j] = {-1, -1};
	DP[1][0] = {1, 0};
	for (int i = 2; i <= n; i++)
	{
		DP[i][0] = {i, 0};
		for (auto u : in[i])
			merge(i, u);
	}
	for (int i = 0; i < q; i++)
	{
		int v, t;
		cin >> v >> t;
		for (int i = 0; i < t; i++)
		{
			cin >> input[i];
			bad[input[i]] = 1;
		}
		if(t >= block)
		{
			memset(dp, -1, sizeof dp);
			dp[v] = 0;
			for (int i = v; i >= 1; i--)
				if(dp[i] != -1)
					for (auto u : in[i])
						dp[u] = max(dp[u], dp[i] + 1);
			int ans = -1;
			for (int i = v; i >= 1; i--)
				if(!bad[i])
					ans = max(ans, dp[i]);
			cout << ans << "\n";
		}
		else
		{
			int ans = -1;
			for (int i = block - 1; i >= 0; i--)
				if(DP[v][i].first != -1 && !bad[DP[v][i].first])
					ans = DP[v][i].second;
			cout << ans << "\n";
		}
		for (int i = 0; i < t; i++)
			bad[input[i]] = 0;
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 3 ms 2680 KB Output is correct
5 Correct 11 ms 5624 KB Output is correct
6 Correct 11 ms 5724 KB Output is correct
7 Correct 11 ms 5624 KB Output is correct
8 Correct 11 ms 5624 KB Output is correct
9 Correct 11 ms 5624 KB Output is correct
10 Correct 12 ms 5624 KB Output is correct
11 Correct 11 ms 5624 KB Output is correct
12 Correct 10 ms 5624 KB Output is correct
13 Correct 10 ms 5624 KB Output is correct
14 Correct 10 ms 5624 KB Output is correct
15 Correct 10 ms 5752 KB Output is correct
16 Correct 10 ms 5624 KB Output is correct
17 Correct 12 ms 5668 KB Output is correct
18 Correct 10 ms 5624 KB Output is correct
19 Correct 10 ms 5624 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 3 ms 2680 KB Output is correct
5 Correct 11 ms 5624 KB Output is correct
6 Correct 11 ms 5724 KB Output is correct
7 Correct 11 ms 5624 KB Output is correct
8 Correct 11 ms 5624 KB Output is correct
9 Correct 11 ms 5624 KB Output is correct
10 Correct 12 ms 5624 KB Output is correct
11 Correct 11 ms 5624 KB Output is correct
12 Correct 10 ms 5624 KB Output is correct
13 Correct 10 ms 5624 KB Output is correct
14 Correct 10 ms 5624 KB Output is correct
15 Correct 10 ms 5752 KB Output is correct
16 Correct 10 ms 5624 KB Output is correct
17 Correct 12 ms 5668 KB Output is correct
18 Correct 10 ms 5624 KB Output is correct
19 Correct 10 ms 5624 KB Output is correct
20 Correct 389 ms 6868 KB Output is correct
21 Correct 402 ms 6864 KB Output is correct
22 Correct 398 ms 6904 KB Output is correct
23 Correct 432 ms 6832 KB Output is correct
24 Correct 897 ms 257428 KB Output is correct
25 Correct 964 ms 257404 KB Output is correct
26 Correct 1064 ms 257312 KB Output is correct
27 Correct 1174 ms 257848 KB Output is correct
28 Correct 1248 ms 257892 KB Output is correct
29 Correct 1299 ms 257716 KB Output is correct
30 Correct 1202 ms 257936 KB Output is correct
31 Correct 1098 ms 257928 KB Output is correct
32 Correct 1240 ms 257628 KB Output is correct
33 Correct 778 ms 257292 KB Output is correct
34 Correct 939 ms 257208 KB Output is correct
35 Correct 793 ms 257132 KB Output is correct
36 Correct 946 ms 257404 KB Output is correct
37 Correct 881 ms 257352 KB Output is correct
38 Correct 888 ms 257192 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 3 ms 2680 KB Output is correct
5 Correct 11 ms 5624 KB Output is correct
6 Correct 11 ms 5724 KB Output is correct
7 Correct 11 ms 5624 KB Output is correct
8 Correct 11 ms 5624 KB Output is correct
9 Correct 11 ms 5624 KB Output is correct
10 Correct 12 ms 5624 KB Output is correct
11 Correct 11 ms 5624 KB Output is correct
12 Correct 10 ms 5624 KB Output is correct
13 Correct 10 ms 5624 KB Output is correct
14 Correct 10 ms 5624 KB Output is correct
15 Correct 10 ms 5752 KB Output is correct
16 Correct 10 ms 5624 KB Output is correct
17 Correct 12 ms 5668 KB Output is correct
18 Correct 10 ms 5624 KB Output is correct
19 Correct 10 ms 5624 KB Output is correct
20 Correct 389 ms 6868 KB Output is correct
21 Correct 402 ms 6864 KB Output is correct
22 Correct 398 ms 6904 KB Output is correct
23 Correct 432 ms 6832 KB Output is correct
24 Correct 897 ms 257428 KB Output is correct
25 Correct 964 ms 257404 KB Output is correct
26 Correct 1064 ms 257312 KB Output is correct
27 Correct 1174 ms 257848 KB Output is correct
28 Correct 1248 ms 257892 KB Output is correct
29 Correct 1299 ms 257716 KB Output is correct
30 Correct 1202 ms 257936 KB Output is correct
31 Correct 1098 ms 257928 KB Output is correct
32 Correct 1240 ms 257628 KB Output is correct
33 Correct 778 ms 257292 KB Output is correct
34 Correct 939 ms 257208 KB Output is correct
35 Correct 793 ms 257132 KB Output is correct
36 Correct 946 ms 257404 KB Output is correct
37 Correct 881 ms 257352 KB Output is correct
38 Correct 888 ms 257192 KB Output is correct
39 Correct 1112 ms 257092 KB Output is correct
40 Incorrect 983 ms 256888 KB Output isn't correct
41 Halted 0 ms 0 KB -