oj.uz

Submission #94458

# Submission time Handle Problem Language Result Execution time Memory
94458 2019-01-18T17:14:48 Z aminra Bitaro’s Party (JOI18_bitaro) C++14
100 / 100
 1838 ms 261608 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;*/
	for (int i = 0; i < block; i++)
		tmp[i] = {-1, -1};
	vector<pair<int, int> > all;
	int ptr1 = 0, ptr2 = 0;
	while(ptr1 < block || ptr2 < block)
	{
		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)))
			all.push_back(DP[a][ptr1++]);
		else
			all.push_back(B), ptr2++;
	}
	int sz = 0;
	for (auto u : all)
		if(u.first != -1 && !prv[u.first])
			tmp[sz++] = u, prv[u.first] = 1;
	for (auto u : all)
			if(u.first != -1)
				prv[u.first] = 0;
	for (int i = 0; i < block; i++)
		DP[a][i] = tmp[i];
}
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 3 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 15 ms 5624 KB Output is correct
6 Correct 16 ms 5624 KB Output is correct
7 Correct 15 ms 5652 KB Output is correct
8 Correct 17 ms 5624 KB Output is correct
9 Correct 17 ms 5624 KB Output is correct
10 Correct 18 ms 5624 KB Output is correct
11 Correct 18 ms 5624 KB Output is correct
12 Correct 17 ms 5624 KB Output is correct
13 Correct 19 ms 5624 KB Output is correct
14 Correct 18 ms 5624 KB Output is correct
15 Correct 18 ms 5752 KB Output is correct
16 Correct 18 ms 5624 KB Output is correct
17 Correct 18 ms 5624 KB Output is correct
18 Correct 18 ms 5624 KB Output is correct
19 Correct 18 ms 5752 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 3 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 15 ms 5624 KB Output is correct
6 Correct 16 ms 5624 KB Output is correct
7 Correct 15 ms 5652 KB Output is correct
8 Correct 17 ms 5624 KB Output is correct
9 Correct 17 ms 5624 KB Output is correct
10 Correct 18 ms 5624 KB Output is correct
11 Correct 18 ms 5624 KB Output is correct
12 Correct 17 ms 5624 KB Output is correct
13 Correct 19 ms 5624 KB Output is correct
14 Correct 18 ms 5624 KB Output is correct
15 Correct 18 ms 5752 KB Output is correct
16 Correct 18 ms 5624 KB Output is correct
17 Correct 18 ms 5624 KB Output is correct
18 Correct 18 ms 5624 KB Output is correct
19 Correct 18 ms 5752 KB Output is correct
20 Correct 1414 ms 6888 KB Output is correct
21 Correct 1333 ms 6776 KB Output is correct
22 Correct 1420 ms 6904 KB Output is correct
23 Correct 1492 ms 6776 KB Output is correct
24 Correct 1718 ms 257436 KB Output is correct
25 Correct 1677 ms 257304 KB Output is correct
26 Correct 1648 ms 257468 KB Output is correct
27 Correct 1807 ms 258048 KB Output is correct
28 Correct 1651 ms 257884 KB Output is correct
29 Correct 1629 ms 257788 KB Output is correct
30 Correct 1631 ms 257964 KB Output is correct
31 Correct 1777 ms 258072 KB Output is correct
32 Correct 1683 ms 257840 KB Output is correct
33 Correct 1542 ms 257552 KB Output is correct
34 Correct 1567 ms 257536 KB Output is correct
35 Correct 1661 ms 257124 KB Output is correct
36 Correct 1541 ms 257356 KB Output is correct
37 Correct 1774 ms 257524 KB Output is correct
38 Correct 1573 ms 257432 KB Output is correct

Subtask #3
86.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 3 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 15 ms 5624 KB Output is correct
6 Correct 16 ms 5624 KB Output is correct
7 Correct 15 ms 5652 KB Output is correct
8 Correct 17 ms 5624 KB Output is correct
9 Correct 17 ms 5624 KB Output is correct
10 Correct 18 ms 5624 KB Output is correct
11 Correct 18 ms 5624 KB Output is correct
12 Correct 17 ms 5624 KB Output is correct
13 Correct 19 ms 5624 KB Output is correct
14 Correct 18 ms 5624 KB Output is correct
15 Correct 18 ms 5752 KB Output is correct
16 Correct 18 ms 5624 KB Output is correct
17 Correct 18 ms 5624 KB Output is correct
18 Correct 18 ms 5624 KB Output is correct
19 Correct 18 ms 5752 KB Output is correct
20 Correct 1414 ms 6888 KB Output is correct
21 Correct 1333 ms 6776 KB Output is correct
22 Correct 1420 ms 6904 KB Output is correct
23 Correct 1492 ms 6776 KB Output is correct
24 Correct 1718 ms 257436 KB Output is correct
25 Correct 1677 ms 257304 KB Output is correct
26 Correct 1648 ms 257468 KB Output is correct
27 Correct 1807 ms 258048 KB Output is correct
28 Correct 1651 ms 257884 KB Output is correct
29 Correct 1629 ms 257788 KB Output is correct
30 Correct 1631 ms 257964 KB Output is correct
31 Correct 1777 ms 258072 KB Output is correct
32 Correct 1683 ms 257840 KB Output is correct
33 Correct 1542 ms 257552 KB Output is correct
34 Correct 1567 ms 257536 KB Output is correct
35 Correct 1661 ms 257124 KB Output is correct
36 Correct 1541 ms 257356 KB Output is correct
37 Correct 1774 ms 257524 KB Output is correct
38 Correct 1573 ms 257432 KB Output is correct
39 Correct 1807 ms 257140 KB Output is correct
40 Correct 1735 ms 256976 KB Output is correct
41 Correct 1685 ms 256844 KB Output is correct
42 Correct 1656 ms 257364 KB Output is correct
43 Correct 1548 ms 257436 KB Output is correct
44 Correct 1465 ms 7004 KB Output is correct
45 Correct 1406 ms 8440 KB Output is correct
46 Correct 1444 ms 8352 KB Output is correct
47 Correct 1413 ms 8696 KB Output is correct
48 Correct 1397 ms 8436 KB Output is correct
49 Correct 1818 ms 260792 KB Output is correct
50 Correct 1769 ms 259576 KB Output is correct
51 Correct 1338 ms 9052 KB Output is correct
52 Correct 1292 ms 8372 KB Output is correct
53 Correct 1575 ms 260196 KB Output is correct
54 Correct 1632 ms 260148 KB Output is correct
55 Correct 1503 ms 259064 KB Output is correct
56 Correct 1500 ms 259100 KB Output is correct
57 Correct 1446 ms 9208 KB Output is correct
58 Correct 1483 ms 9208 KB Output is correct
59 Correct 1416 ms 8312 KB Output is correct
60 Correct 1282 ms 8184 KB Output is correct
61 Correct 1675 ms 259908 KB Output is correct
62 Correct 1513 ms 259604 KB Output is correct
63 Correct 1574 ms 259544 KB Output is correct
64 Correct 1714 ms 260096 KB Output is correct
65 Correct 1560 ms 259512 KB Output is correct
66 Correct 1838 ms 259632 KB Output is correct
67 Correct 1719 ms 259492 KB Output is correct
68 Correct 1551 ms 259092 KB Output is correct
69 Correct 1631 ms 259080 KB Output is correct
70 Correct 1667 ms 260172 KB Output is correct
71 Correct 1583 ms 259832 KB Output is correct
72 Correct 1662 ms 259768 KB Output is correct
73 Correct 1761 ms 260100 KB Output is correct
74 Correct 1552 ms 259748 KB Output is correct
75 Correct 1654 ms 259640 KB Output is correct
76 Correct 1695 ms 261496 KB Output is correct
77 Correct 1585 ms 260388 KB Output is correct
78 Correct 1649 ms 260768 KB Output is correct
79 Correct 1345 ms 9336 KB Output is correct
80 Correct 1279 ms 8440 KB Output is correct
81 Correct 1369 ms 8440 KB Output is correct
82 Correct 1722 ms 261608 KB Output is correct
83 Correct 1791 ms 261560 KB Output is correct
84 Correct 1564 ms 260088 KB Output is correct
85 Correct 1745 ms 260256 KB Output is correct
86 Correct 1821 ms 260840 KB Output is correct
87 Correct 1783 ms 260728 KB Output is correct
88 Correct 1480 ms 9208 KB Output is correct
89 Correct 1506 ms 9212 KB Output is correct
90 Correct 1316 ms 8440 KB Output is correct
91 Correct 1409 ms 8440 KB Output is correct
92 Correct 1338 ms 8312 KB Output is correct
93 Correct 1408 ms 8440 KB Output is correct
94 Correct 1751 ms 260852 KB Output is correct
95 Correct 1719 ms 260764 KB Output is correct
96 Correct 1644 ms 259704 KB Output is correct
97 Correct 1646 ms 259696 KB Output is correct
98 Correct 1562 ms 260248 KB Output is correct
99 Correct 1486 ms 260216 KB Output is correct
100 Correct 1534 ms 9336 KB Output is correct
101 Correct 1459 ms 9244 KB Output is correct
102 Correct 1445 ms 8440 KB Output is correct
103 Correct 1481 ms 8368 KB Output is correct
104 Correct 1487 ms 8440 KB Output is correct
105 Correct 1485 ms 8368 KB Output is correct
106 Correct 1587 ms 260996 KB Output is correct
107 Correct 1788 ms 260876 KB Output is correct
108 Correct 1519 ms 259832 KB Output is correct
109 Correct 1569 ms 259856 KB Output is correct
110 Correct 1507 ms 260112 KB Output is correct
111 Correct 1600 ms 260344 KB Output is correct
112 Correct 1516 ms 9336 KB Output is correct
113 Correct 1534 ms 9464 KB Output is correct
114 Correct 1424 ms 8440 KB Output is correct
115 Correct 1409 ms 8316 KB Output is correct
116 Correct 1428 ms 8440 KB Output is correct
117 Correct 1381 ms 8416 KB Output is correct
118 Correct 1611 ms 259516 KB Output is correct
119 Correct 1471 ms 259120 KB Output is correct
120 Correct 1549 ms 259164 KB Output is correct
121 Correct 1687 ms 259636 KB Output is correct
122 Correct 1671 ms 259068 KB Output is correct
123 Correct 1639 ms 259084 KB Output is correct
124 Correct 1686 ms 259576 KB Output is correct
125 Correct 1554 ms 259180 KB Output is correct
126 Correct 1604 ms 259056 KB Output is correct