oj.uz

Submission #95065

# Submission time Handle Problem Language Result Execution time Memory
95065 2019-01-27T07:37:32 Z ImaniAm Bitaro’s Party (JOI18_bitaro) C++14
14 / 100
 2000 ms 461260 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back

typedef pair <int, int> pii;

const int maxn = 1e5 + 10, maxm = 2e5 + 10, sq = 320;
int n, m, q, size[maxn], h[maxn], input[maxn];
vector <pii> mx[maxn], vec;
vector <int> in[maxn];
bitset <maxn> mark;

bool cmp(const pii &p1, const pii &p2) {
	return p1 > p2;
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m >> q;
	for (int i = 0, v, u; i < m; ++i) {
		cin >> v >> u;
		in[--u].pb(--v);
	}
	for (int i = 0; i < n; ++i) {
		mx[i].pb({-1, i});
		for (auto j: in[i]) {
			int se = mx[i].size(), se2 = mx[j].size();
			vec.resize(se + se2);
			merge(mx[i].begin(), mx[i].end(), mx[j].begin(), mx[j].end(), vec.begin(), cmp);
			if (int(vec.size()) > sq)
				vec.resize(sq);
			mx[i].swap(vec);
		}
		size[i] = mx[i].size();
		for (int j = 0; j < size[i]; ++j)
			mx[i][j].first++;
	}
	for (int i = 0, v, num; i < q; ++i) {
		cin >> v >> num; --v;
		for (int j = 0; j < num; ++j) {
			cin >> input[j];
			mark[--input[j]] = true;
		}
		int ans = -1;
		for (int j = 0; j < size[v]; ++j)
			if (!mark[mx[v][j].second]) {
				ans = mx[v][j].first;
				break;
			}
		if (ans == -1) {
			memset(h, -63, sizeof(h));
			h[v] = 0;
			for (int j = v; ~j; --j) {
				if (!mark[j])
					ans = max(ans, h[j]);
				for (auto u: in[j])
					h[u] = max(h[u], h[j] + 1);
			}
		}
		cout << ans << '\n';
		for (int j = 0; j < num; ++j)
			mark[input[j]] = false;
	}
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5368 KB Output is correct
3 Correct 6 ms 5368 KB Output is correct
4 Correct 6 ms 5368 KB Output is correct
5 Correct 11 ms 7672 KB Output is correct
6 Correct 11 ms 7160 KB Output is correct
7 Correct 11 ms 7288 KB Output is correct
8 Correct 14 ms 9476 KB Output is correct
9 Correct 14 ms 9468 KB Output is correct
10 Correct 14 ms 9848 KB Output is correct
11 Correct 13 ms 9208 KB Output is correct
12 Correct 12 ms 7672 KB Output is correct
13 Correct 15 ms 9720 KB Output is correct
14 Correct 11 ms 7800 KB Output is correct
15 Correct 9 ms 6264 KB Output is correct
16 Correct 10 ms 7288 KB Output is correct
17 Correct 12 ms 8312 KB Output is correct
18 Correct 10 ms 6904 KB Output is correct
19 Correct 12 ms 8824 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5368 KB Output is correct
3 Correct 6 ms 5368 KB Output is correct
4 Correct 6 ms 5368 KB Output is correct
5 Correct 11 ms 7672 KB Output is correct
6 Correct 11 ms 7160 KB Output is correct
7 Correct 11 ms 7288 KB Output is correct
8 Correct 14 ms 9476 KB Output is correct
9 Correct 14 ms 9468 KB Output is correct
10 Correct 14 ms 9848 KB Output is correct
11 Correct 13 ms 9208 KB Output is correct
12 Correct 12 ms 7672 KB Output is correct
13 Correct 15 ms 9720 KB Output is correct
14 Correct 11 ms 7800 KB Output is correct
15 Correct 9 ms 6264 KB Output is correct
16 Correct 10 ms 7288 KB Output is correct
17 Correct 12 ms 8312 KB Output is correct
18 Correct 10 ms 6904 KB Output is correct
19 Correct 12 ms 8824 KB Output is correct
20 Correct 331 ms 11704 KB Output is correct
21 Correct 324 ms 11324 KB Output is correct
22 Correct 322 ms 11768 KB Output is correct
23 Correct 321 ms 11144 KB Output is correct
24 Correct 1053 ms 355064 KB Output is correct
25 Correct 954 ms 354680 KB Output is correct
26 Correct 905 ms 355532 KB Output is correct
27 Correct 970 ms 458776 KB Output is correct
28 Correct 1033 ms 458884 KB Output is correct
29 Correct 963 ms 459604 KB Output is correct
30 Correct 993 ms 458848 KB Output is correct
31 Correct 998 ms 437912 KB Output is correct
32 Correct 972 ms 459668 KB Output is correct
33 Correct 654 ms 271904 KB Output is correct
34 Correct 667 ms 229356 KB Output is correct
35 Correct 687 ms 270504 KB Output is correct
36 Correct 894 ms 373724 KB Output is correct
37 Correct 827 ms 338424 KB Output is correct
38 Correct 828 ms 374000 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5368 KB Output is correct
3 Correct 6 ms 5368 KB Output is correct
4 Correct 6 ms 5368 KB Output is correct
5 Correct 11 ms 7672 KB Output is correct
6 Correct 11 ms 7160 KB Output is correct
7 Correct 11 ms 7288 KB Output is correct
8 Correct 14 ms 9476 KB Output is correct
9 Correct 14 ms 9468 KB Output is correct
10 Correct 14 ms 9848 KB Output is correct
11 Correct 13 ms 9208 KB Output is correct
12 Correct 12 ms 7672 KB Output is correct
13 Correct 15 ms 9720 KB Output is correct
14 Correct 11 ms 7800 KB Output is correct
15 Correct 9 ms 6264 KB Output is correct
16 Correct 10 ms 7288 KB Output is correct
17 Correct 12 ms 8312 KB Output is correct
18 Correct 10 ms 6904 KB Output is correct
19 Correct 12 ms 8824 KB Output is correct
20 Correct 331 ms 11704 KB Output is correct
21 Correct 324 ms 11324 KB Output is correct
22 Correct 322 ms 11768 KB Output is correct
23 Correct 321 ms 11144 KB Output is correct
24 Correct 1053 ms 355064 KB Output is correct
25 Correct 954 ms 354680 KB Output is correct
26 Correct 905 ms 355532 KB Output is correct
27 Correct 970 ms 458776 KB Output is correct
28 Correct 1033 ms 458884 KB Output is correct
29 Correct 963 ms 459604 KB Output is correct
30 Correct 993 ms 458848 KB Output is correct
31 Correct 998 ms 437912 KB Output is correct
32 Correct 972 ms 459668 KB Output is correct
33 Correct 654 ms 271904 KB Output is correct
34 Correct 667 ms 229356 KB Output is correct
35 Correct 687 ms 270504 KB Output is correct
36 Correct 894 ms 373724 KB Output is correct
37 Correct 827 ms 338424 KB Output is correct
38 Correct 828 ms 374000 KB Output is correct
39 Correct 1016 ms 350560 KB Output is correct
40 Correct 985 ms 354768 KB Output is correct
41 Correct 1000 ms 354496 KB Output is correct
42 Correct 1092 ms 353796 KB Output is correct
43 Correct 865 ms 353560 KB Output is correct
44 Correct 378 ms 14468 KB Output is correct
45 Correct 347 ms 13640 KB Output is correct
46 Correct 345 ms 13560 KB Output is correct
47 Correct 331 ms 13300 KB Output is correct
48 Correct 327 ms 13392 KB Output is correct
49 Execution timed out 2071 ms 461260 KB Time limit exceeded
50 Halted 0 ms 0 KB -