oj.uz

Submission #212830

# Submission time Handle Problem Language Result Execution time Memory
212830 2020-03-24T11:37:17 Z faremy Bitaro’s Party (JOI18_bitaro) C++14
100 / 100
 1835 ms 263216 KB 
#include <iostream>
#include <algorithm>
#include <vector>


struct Beaver
{
	Beaver(int i, int d) : id(i), dist(d) {}
	int id, dist;
};

const int MAXN = 1e5;
const int SQRT = 317;

std::vector<int> graph[MAXN];
std::vector<Beaver> furthest[MAXN];
bool seen[MAXN];
bool busy[MAXN];
int maxDist[MAXN];


void append(std::vector<Beaver> &vec, Beaver elem)
{
	if (!seen[elem.id])
	{
		vec.emplace_back(elem);
		seen[elem.id] = true;
	}
}

void merge(int parent, int child)
{
	std::vector<Beaver> merged;
	int left = 0, right = 0;

	while (merged.size() < SQRT && (left < (int)furthest[parent].size() || right < (int)furthest[child].size()))
	{
		if (left == (int)furthest[parent].size())
		{
			append(merged, Beaver(furthest[child][right].id, furthest[child][right].dist + 1));
			right++;
		}
		else if (right == (int)furthest[child].size())
		{
			append(merged, furthest[parent][left]);
			left++;
		}
		else if (furthest[parent][left].dist > furthest[child][right].dist + 1)
		{
			append(merged, furthest[parent][left]);
			left++;
		}
		else
		{
			append(merged, Beaver(furthest[child][right].id, furthest[child][right].dist + 1));
			right++;
		}
	}

	for (Beaver beav : merged)
		seen[beav.id] = false;
	furthest[parent] = merged;
}

int slowcheck(int node)
{
	if (seen[node])
		return maxDist[node];
	seen[node] = true;

	if (busy[node])
		maxDist[node] = -1;
	else
		maxDist[node] = 0;

	for (int child : graph[node])
	{
		int sub = slowcheck(child);
		if (sub != -1)
			maxDist[node] = std::max(maxDist[node], sub + 1);
	}

	return maxDist[node];
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cout.tie(nullptr);
	std::cin.tie(nullptr);

	int nodes, edges, queries;
	std::cin >> nodes >> edges >> queries;

	for (int iEdge = 0; iEdge < edges; iEdge++)
	{
		int u, v;
		std::cin >> u >> v;
		graph[v - 1].emplace_back(u - 1);
	}

	for (int iNode = 0; iNode < nodes; iNode++)
	{
		furthest[iNode].emplace_back(iNode, 0);
		for (int child : graph[iNode])
			merge(iNode, child);
	}

	for (int iQuery = 0; iQuery < queries; iQuery++)
	{
		int location, unable;
		std::cin >> location >> unable;
		location--;

		std::vector<int> notComing;
		for (int iFriend = 0; iFriend < unable; iFriend++)
		{
			int beaver; std::cin >> beaver;
			notComing.emplace_back(beaver - 1);
			busy[beaver - 1] = true;
		}

		if (unable < SQRT)
		{
			int far = 0;
			while (far < (int)furthest[location].size() && busy[furthest[location][far].id])
				far++;

			if (far == (int)furthest[location].size())
				std::cout << "-1\n";
			else
				std::cout << furthest[location][far].dist << '\n';
		}
		else
		{
			std::fill_n(seen, nodes, false);
			std::cout << slowcheck(location) << '\n';
		}

		for (int beaver : notComing)
			busy[beaver] = false;
	}

	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 9 ms 5120 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 10 ms 5376 KB Output is correct
6 Correct 10 ms 5376 KB Output is correct
7 Correct 10 ms 5376 KB Output is correct
8 Correct 19 ms 7168 KB Output is correct
9 Correct 18 ms 7168 KB Output is correct
10 Correct 19 ms 7168 KB Output is correct
11 Correct 19 ms 6912 KB Output is correct
12 Correct 13 ms 6016 KB Output is correct
13 Correct 19 ms 6912 KB Output is correct
14 Correct 17 ms 6144 KB Output is correct
15 Correct 13 ms 5760 KB Output is correct
16 Correct 17 ms 6272 KB Output is correct
17 Correct 16 ms 6528 KB Output is correct
18 Correct 13 ms 5888 KB Output is correct
19 Correct 17 ms 6528 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 9 ms 5120 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 10 ms 5376 KB Output is correct
6 Correct 10 ms 5376 KB Output is correct
7 Correct 10 ms 5376 KB Output is correct
8 Correct 19 ms 7168 KB Output is correct
9 Correct 18 ms 7168 KB Output is correct
10 Correct 19 ms 7168 KB Output is correct
11 Correct 19 ms 6912 KB Output is correct
12 Correct 13 ms 6016 KB Output is correct
13 Correct 19 ms 6912 KB Output is correct
14 Correct 17 ms 6144 KB Output is correct
15 Correct 13 ms 5760 KB Output is correct
16 Correct 17 ms 6272 KB Output is correct
17 Correct 16 ms 6528 KB Output is correct
18 Correct 13 ms 5888 KB Output is correct
19 Correct 17 ms 6528 KB Output is correct
20 Correct 1138 ms 8600 KB Output is correct
21 Correct 1039 ms 8372 KB Output is correct
22 Correct 1093 ms 8440 KB Output is correct
23 Correct 1166 ms 8580 KB Output is correct
24 Correct 1081 ms 162304 KB Output is correct
25 Correct 1145 ms 169336 KB Output is correct
26 Correct 1128 ms 169260 KB Output is correct
27 Correct 1338 ms 259304 KB Output is correct
28 Correct 1314 ms 259660 KB Output is correct
29 Correct 1325 ms 260212 KB Output is correct
30 Correct 1316 ms 257172 KB Output is correct
31 Correct 1310 ms 248820 KB Output is correct
32 Correct 1340 ms 257212 KB Output is correct
33 Correct 1108 ms 159992 KB Output is correct
34 Correct 1002 ms 132468 KB Output is correct
35 Correct 1101 ms 158948 KB Output is correct
36 Correct 1275 ms 208792 KB Output is correct
37 Correct 1187 ms 189824 KB Output is correct
38 Correct 1249 ms 209272 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 9 ms 5120 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 10 ms 5376 KB Output is correct
6 Correct 10 ms 5376 KB Output is correct
7 Correct 10 ms 5376 KB Output is correct
8 Correct 19 ms 7168 KB Output is correct
9 Correct 18 ms 7168 KB Output is correct
10 Correct 19 ms 7168 KB Output is correct
11 Correct 19 ms 6912 KB Output is correct
12 Correct 13 ms 6016 KB Output is correct
13 Correct 19 ms 6912 KB Output is correct
14 Correct 17 ms 6144 KB Output is correct
15 Correct 13 ms 5760 KB Output is correct
16 Correct 17 ms 6272 KB Output is correct
17 Correct 16 ms 6528 KB Output is correct
18 Correct 13 ms 5888 KB Output is correct
19 Correct 17 ms 6528 KB Output is correct
20 Correct 1138 ms 8600 KB Output is correct
21 Correct 1039 ms 8372 KB Output is correct
22 Correct 1093 ms 8440 KB Output is correct
23 Correct 1166 ms 8580 KB Output is correct
24 Correct 1081 ms 162304 KB Output is correct
25 Correct 1145 ms 169336 KB Output is correct
26 Correct 1128 ms 169260 KB Output is correct
27 Correct 1338 ms 259304 KB Output is correct
28 Correct 1314 ms 259660 KB Output is correct
29 Correct 1325 ms 260212 KB Output is correct
30 Correct 1316 ms 257172 KB Output is correct
31 Correct 1310 ms 248820 KB Output is correct
32 Correct 1340 ms 257212 KB Output is correct
33 Correct 1108 ms 159992 KB Output is correct
34 Correct 1002 ms 132468 KB Output is correct
35 Correct 1101 ms 158948 KB Output is correct
36 Correct 1275 ms 208792 KB Output is correct
37 Correct 1187 ms 189824 KB Output is correct
38 Correct 1249 ms 209272 KB Output is correct
39 Correct 1189 ms 164028 KB Output is correct
40 Correct 1187 ms 165460 KB Output is correct
41 Correct 1165 ms 166740 KB Output is correct
42 Correct 1158 ms 166504 KB Output is correct
43 Correct 1156 ms 165712 KB Output is correct
44 Correct 1153 ms 8876 KB Output is correct
45 Correct 1110 ms 8440 KB Output is correct
46 Correct 1115 ms 8528 KB Output is correct
47 Correct 1129 ms 8440 KB Output is correct
48 Correct 1135 ms 8568 KB Output is correct
49 Correct 1489 ms 257400 KB Output is correct
50 Correct 1472 ms 256888 KB Output is correct
51 Correct 1086 ms 8824 KB Output is correct
52 Correct 1048 ms 8312 KB Output is correct
53 Correct 1384 ms 208024 KB Output is correct
54 Correct 1325 ms 189816 KB Output is correct
55 Correct 1314 ms 207924 KB Output is correct
56 Correct 1246 ms 190072 KB Output is correct
57 Correct 1139 ms 8756 KB Output is correct
58 Correct 1192 ms 8824 KB Output is correct
59 Correct 1113 ms 8568 KB Output is correct
60 Correct 1153 ms 8568 KB Output is correct
61 Correct 1629 ms 260444 KB Output is correct
62 Correct 1435 ms 208760 KB Output is correct
63 Correct 1317 ms 189516 KB Output is correct
64 Correct 1835 ms 260684 KB Output is correct
65 Correct 1612 ms 207992 KB Output is correct
66 Correct 1429 ms 190512 KB Output is correct
67 Correct 1427 ms 256888 KB Output is correct
68 Correct 1328 ms 211192 KB Output is correct
69 Correct 1233 ms 190256 KB Output is correct
70 Correct 1418 ms 263032 KB Output is correct
71 Correct 1323 ms 211448 KB Output is correct
72 Correct 1292 ms 192908 KB Output is correct
73 Correct 1508 ms 263160 KB Output is correct
74 Correct 1377 ms 211704 KB Output is correct
75 Correct 1281 ms 192888 KB Output is correct
76 Correct 1469 ms 261500 KB Output is correct
77 Correct 1419 ms 259960 KB Output is correct
78 Correct 1367 ms 263216 KB Output is correct
79 Correct 1126 ms 11384 KB Output is correct
80 Correct 1031 ms 10308 KB Output is correct
81 Correct 1038 ms 9916 KB Output is correct
82 Correct 1458 ms 260984 KB Output is correct
83 Correct 1488 ms 252536 KB Output is correct
84 Correct 1408 ms 259576 KB Output is correct
85 Correct 1405 ms 251128 KB Output is correct
86 Correct 1372 ms 260780 KB Output is correct
87 Correct 1342 ms 252428 KB Output is correct
88 Correct 1150 ms 11484 KB Output is correct
89 Correct 1183 ms 11512 KB Output is correct
90 Correct 1128 ms 10616 KB Output is correct
91 Correct 1142 ms 10488 KB Output is correct
92 Correct 1124 ms 9996 KB Output is correct
93 Correct 1089 ms 10104 KB Output is correct
94 Correct 1204 ms 163896 KB Output is correct
95 Correct 1067 ms 135644 KB Output is correct
96 Correct 1119 ms 161836 KB Output is correct
97 Correct 1029 ms 136696 KB Output is correct
98 Correct 1111 ms 162860 KB Output is correct
99 Correct 1008 ms 136696 KB Output is correct
100 Correct 1232 ms 11360 KB Output is correct
101 Correct 1215 ms 11208 KB Output is correct
102 Correct 1204 ms 10360 KB Output is correct
103 Correct 1195 ms 10488 KB Output is correct
104 Correct 1178 ms 10232 KB Output is correct
105 Correct 1207 ms 10140 KB Output is correct
106 Correct 1378 ms 211832 KB Output is correct
107 Correct 1302 ms 193624 KB Output is correct
108 Correct 1318 ms 211832 KB Output is correct
109 Correct 1249 ms 192376 KB Output is correct
110 Correct 1279 ms 212600 KB Output is correct
111 Correct 1199 ms 193384 KB Output is correct
112 Correct 1147 ms 11256 KB Output is correct
113 Correct 1194 ms 11228 KB Output is correct
114 Correct 1117 ms 10316 KB Output is correct
115 Correct 1142 ms 10388 KB Output is correct
116 Correct 1120 ms 9936 KB Output is correct
117 Correct 1115 ms 9988 KB Output is correct
118 Correct 1396 ms 259576 KB Output is correct
119 Correct 1326 ms 211448 KB Output is correct
120 Correct 1246 ms 192120 KB Output is correct
121 Correct 1413 ms 259576 KB Output is correct
122 Correct 1329 ms 210808 KB Output is correct
123 Correct 1272 ms 191992 KB Output is correct
124 Correct 1393 ms 259576 KB Output is correct
125 Correct 1315 ms 211576 KB Output is correct
126 Correct 1246 ms 191224 KB Output is correct