oj.uz

답안 #479227

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
479227 2021-10-10T22:27:46 Z s_samchenko Bitaro’s Party (JOI18_bitaro) C++17
100 / 100
 1796 ms 413168 KB 
#include "bits/stdc++.h"

using namespace std;

using ll = long long;

const int SQRT = 350;
const int maxN = 1e5;

int dp[maxN + 5];
vector<int> adj[maxN + 5];
vector<pair<int, int>> root[maxN + 5];

int n, m, q;

void build(){
	vector<int> cost(n + 5, 0);
	vector<int> visited(n + 5, -1);

	for (int i = 1; i <= n; ++i){
		vector<int> r;
		for (int j : adj[i]){
			for (auto e : root[j]){
				int k = e.first, c = e.second;
				if (visited[k] == i)
					cost[k]= max(cost[k], c + 1);
				else{
					r.push_back(k);
					cost[k] = c + 1;
					visited[k] = i;
				}
			}
			if (visited[j] != i){
				r.push_back(j);
				cost[j] = 1;
				visited[j] = i;
			}
		}
		r.push_back(i);

		sort(r.begin(), r.end(), [&](int a, int b){
			return (cost[a] > cost[b]);
		});
		int sz = min(int(r.size()), SQRT);
		for (int j = 0; j < sz; ++j){
			int p = r[j];
			root[i].push_back({p, cost[p]});
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> q;
	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		adj[b].push_back(a);
	}


	build();

	vector<int> queries(n + 5, 0);

	for (int i = 1; i <= q; ++i){
		int t; cin >> t;
		int sz; cin >> sz;
		for (int j = 1; j <= sz; ++j){
			int x; cin >> x;
			queries[x] = i;
		}

		if (sz < SQRT){
			bool f = 0;
			for (auto e : root[t]){
				if (queries[e.first] == i) continue;
				cout << e.second << '\n';
				f = 1;
				break;
			}
			if (!f) cout << -1 << '\n';
		}
		else{
			for (int j = 1; j <= n; ++j){
				if (queries[j] != i) dp[j] = 0;
				else dp[j] = -1;
				for (int k : adj[j])
					if (dp[k] >= 0) dp[j] = max(dp[j], dp[k] + 1);
			}
			cout << dp[t] << '\n';
		}
	}
	return 0;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 6 ms 5452 KB Output is correct
6 Correct 6 ms 5452 KB Output is correct
7 Correct 7 ms 5476 KB Output is correct
8 Correct 18 ms 8296 KB Output is correct
9 Correct 16 ms 8408 KB Output is correct
10 Correct 16 ms 8320 KB Output is correct
11 Correct 15 ms 8020 KB Output is correct
12 Correct 9 ms 6220 KB Output is correct
13 Correct 14 ms 7732 KB Output is correct
14 Correct 13 ms 7024 KB Output is correct
15 Correct 9 ms 5924 KB Output is correct
16 Correct 12 ms 6860 KB Output is correct
17 Correct 12 ms 7244 KB Output is correct
18 Correct 9 ms 6092 KB Output is correct
19 Correct 13 ms 7240 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 6 ms 5452 KB Output is correct
6 Correct 6 ms 5452 KB Output is correct
7 Correct 7 ms 5476 KB Output is correct
8 Correct 18 ms 8296 KB Output is correct
9 Correct 16 ms 8408 KB Output is correct
10 Correct 16 ms 8320 KB Output is correct
11 Correct 15 ms 8020 KB Output is correct
12 Correct 9 ms 6220 KB Output is correct
13 Correct 14 ms 7732 KB Output is correct
14 Correct 13 ms 7024 KB Output is correct
15 Correct 9 ms 5924 KB Output is correct
16 Correct 12 ms 6860 KB Output is correct
17 Correct 12 ms 7244 KB Output is correct
18 Correct 9 ms 6092 KB Output is correct
19 Correct 13 ms 7240 KB Output is correct
20 Correct 240 ms 9472 KB Output is correct
21 Correct 241 ms 9472 KB Output is correct
22 Correct 249 ms 9436 KB Output is correct
23 Correct 288 ms 9524 KB Output is correct
24 Correct 1317 ms 252612 KB Output is correct
25 Correct 1359 ms 264008 KB Output is correct
26 Correct 1330 ms 263156 KB Output is correct
27 Correct 1667 ms 410668 KB Output is correct
28 Correct 1604 ms 411184 KB Output is correct
29 Correct 1571 ms 411268 KB Output is correct
30 Correct 1670 ms 410856 KB Output is correct
31 Correct 1762 ms 396456 KB Output is correct
32 Correct 1623 ms 410780 KB Output is correct
33 Correct 1184 ms 253124 KB Output is correct
34 Correct 1192 ms 206944 KB Output is correct
35 Correct 1215 ms 251400 KB Output is correct
36 Correct 1421 ms 331952 KB Output is correct
37 Correct 1521 ms 300348 KB Output is correct
38 Correct 1401 ms 333064 KB Output is correct

Subtask #3
86.0 / 86.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 6 ms 5452 KB Output is correct
6 Correct 6 ms 5452 KB Output is correct
7 Correct 7 ms 5476 KB Output is correct
8 Correct 18 ms 8296 KB Output is correct
9 Correct 16 ms 8408 KB Output is correct
10 Correct 16 ms 8320 KB Output is correct
11 Correct 15 ms 8020 KB Output is correct
12 Correct 9 ms 6220 KB Output is correct
13 Correct 14 ms 7732 KB Output is correct
14 Correct 13 ms 7024 KB Output is correct
15 Correct 9 ms 5924 KB Output is correct
16 Correct 12 ms 6860 KB Output is correct
17 Correct 12 ms 7244 KB Output is correct
18 Correct 9 ms 6092 KB Output is correct
19 Correct 13 ms 7240 KB Output is correct
20 Correct 240 ms 9472 KB Output is correct
21 Correct 241 ms 9472 KB Output is correct
22 Correct 249 ms 9436 KB Output is correct
23 Correct 288 ms 9524 KB Output is correct
24 Correct 1317 ms 252612 KB Output is correct
25 Correct 1359 ms 264008 KB Output is correct
26 Correct 1330 ms 263156 KB Output is correct
27 Correct 1667 ms 410668 KB Output is correct
28 Correct 1604 ms 411184 KB Output is correct
29 Correct 1571 ms 411268 KB Output is correct
30 Correct 1670 ms 410856 KB Output is correct
31 Correct 1762 ms 396456 KB Output is correct
32 Correct 1623 ms 410780 KB Output is correct
33 Correct 1184 ms 253124 KB Output is correct
34 Correct 1192 ms 206944 KB Output is correct
35 Correct 1215 ms 251400 KB Output is correct
36 Correct 1421 ms 331952 KB Output is correct
37 Correct 1521 ms 300348 KB Output is correct
38 Correct 1401 ms 333064 KB Output is correct
39 Correct 1406 ms 256228 KB Output is correct
40 Correct 1357 ms 260604 KB Output is correct
41 Correct 1392 ms 263484 KB Output is correct
42 Correct 1482 ms 261272 KB Output is correct
43 Correct 1350 ms 260528 KB Output is correct
44 Correct 274 ms 11968 KB Output is correct
45 Correct 248 ms 11472 KB Output is correct
46 Correct 243 ms 11396 KB Output is correct
47 Correct 312 ms 11204 KB Output is correct
48 Correct 241 ms 11124 KB Output is correct
49 Correct 1632 ms 412996 KB Output is correct
50 Correct 1561 ms 412920 KB Output is correct
51 Correct 286 ms 12060 KB Output is correct
52 Correct 240 ms 11332 KB Output is correct
53 Correct 1418 ms 332356 KB Output is correct
54 Correct 1525 ms 302416 KB Output is correct
55 Correct 1367 ms 332860 KB Output is correct
56 Correct 1490 ms 303108 KB Output is correct
57 Correct 258 ms 12100 KB Output is correct
58 Correct 250 ms 12020 KB Output is correct
59 Correct 237 ms 11332 KB Output is correct
60 Correct 236 ms 11288 KB Output is correct
61 Correct 1662 ms 413004 KB Output is correct
62 Correct 1507 ms 334096 KB Output is correct
63 Correct 1617 ms 301660 KB Output is correct
64 Correct 1624 ms 413000 KB Output is correct
65 Correct 1431 ms 332616 KB Output is correct
66 Correct 1607 ms 303248 KB Output is correct
67 Correct 1572 ms 412808 KB Output is correct
68 Correct 1378 ms 334116 KB Output is correct
69 Correct 1462 ms 299372 KB Output is correct
70 Correct 1559 ms 412896 KB Output is correct
71 Correct 1421 ms 334184 KB Output is correct
72 Correct 1495 ms 302560 KB Output is correct
73 Correct 1596 ms 412996 KB Output is correct
74 Correct 1452 ms 334128 KB Output is correct
75 Correct 1493 ms 302852 KB Output is correct
76 Correct 1619 ms 413028 KB Output is correct
77 Correct 1547 ms 413148 KB Output is correct
78 Correct 1579 ms 412952 KB Output is correct
79 Correct 266 ms 12060 KB Output is correct
80 Correct 235 ms 11332 KB Output is correct
81 Correct 247 ms 10996 KB Output is correct
82 Correct 1622 ms 412716 KB Output is correct
83 Correct 1796 ms 399520 KB Output is correct
84 Correct 1572 ms 412580 KB Output is correct
85 Correct 1743 ms 398056 KB Output is correct
86 Correct 1565 ms 413072 KB Output is correct
87 Correct 1712 ms 399252 KB Output is correct
88 Correct 258 ms 12332 KB Output is correct
89 Correct 259 ms 12340 KB Output is correct
90 Correct 242 ms 11460 KB Output is correct
91 Correct 242 ms 11376 KB Output is correct
92 Correct 236 ms 11076 KB Output is correct
93 Correct 238 ms 11044 KB Output is correct
94 Correct 1181 ms 256524 KB Output is correct
95 Correct 1235 ms 208860 KB Output is correct
96 Correct 1120 ms 254112 KB Output is correct
97 Correct 1193 ms 212100 KB Output is correct
98 Correct 1136 ms 255108 KB Output is correct
99 Correct 1185 ms 211660 KB Output is correct
100 Correct 294 ms 12356 KB Output is correct
101 Correct 290 ms 12388 KB Output is correct
102 Correct 278 ms 11476 KB Output is correct
103 Correct 279 ms 11424 KB Output is correct
104 Correct 273 ms 11076 KB Output is correct
105 Correct 278 ms 11040 KB Output is correct
106 Correct 1404 ms 334012 KB Output is correct
107 Correct 1492 ms 303964 KB Output is correct
108 Correct 1366 ms 335244 KB Output is correct
109 Correct 1394 ms 302588 KB Output is correct
110 Correct 1364 ms 335616 KB Output is correct
111 Correct 1513 ms 303884 KB Output is correct
112 Correct 247 ms 12612 KB Output is correct
113 Correct 267 ms 12384 KB Output is correct
114 Correct 244 ms 11436 KB Output is correct
115 Correct 238 ms 11404 KB Output is correct
116 Correct 229 ms 11120 KB Output is correct
117 Correct 244 ms 11016 KB Output is correct
118 Correct 1570 ms 413116 KB Output is correct
119 Correct 1475 ms 335048 KB Output is correct
120 Correct 1460 ms 302252 KB Output is correct
121 Correct 1554 ms 413168 KB Output is correct
122 Correct 1407 ms 333488 KB Output is correct
123 Correct 1465 ms 302448 KB Output is correct
124 Correct 1535 ms 412984 KB Output is correct
125 Correct 1366 ms 335160 KB Output is correct
126 Correct 1434 ms 301328 KB Output is correct