답안 #94445 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94445	2019-01-18T14:57:53 Z	aminra	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	697 ms	260272 KB

bitaro

//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];
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;
}
void merge(int a, int b)
{
	for (int i = 0; i < block; i++)
		tmp[i] = {-1, -1};
	int ptr1 = 0, ptr2 = 0;
	while(ptr1 + ptr2 < block)
	{
		pair<int, int> B = DP[b][ptr2];
		if(B.second != -1)
			B.second++;
		if(cmp(DP[a][ptr1], B))
			tmp[ptr1 + ptr2] = DP[a][ptr1], ptr1++;
		else
			tmp[ptr1 + ptr2] = B, ptr2++;
	}
	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;
		}
		//answer query.
		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

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2680 KB	Output is correct
2	Correct	3 ms	2680 KB	Output is correct
3	Correct	3 ms	2680 KB	Output is correct
4	Correct	3 ms	2680 KB	Output is correct
5	Correct	8 ms	5624 KB	Output is correct
6	Correct	8 ms	5624 KB	Output is correct
7	Correct	8 ms	5624 KB	Output is correct
8	Correct	9 ms	5624 KB	Output is correct
9	Correct	9 ms	5624 KB	Output is correct
10	Correct	9 ms	5624 KB	Output is correct
11	Correct	9 ms	5624 KB	Output is correct
12	Correct	9 ms	5624 KB	Output is correct
13	Correct	9 ms	5624 KB	Output is correct
14	Correct	9 ms	5624 KB	Output is correct
15	Correct	9 ms	5624 KB	Output is correct
16	Correct	9 ms	5624 KB	Output is correct
17	Correct	9 ms	5616 KB	Output is correct
18	Correct	9 ms	5652 KB	Output is correct
19	Correct	9 ms	5624 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2680 KB	Output is correct
2	Correct	3 ms	2680 KB	Output is correct
3	Correct	3 ms	2680 KB	Output is correct
4	Correct	3 ms	2680 KB	Output is correct
5	Correct	8 ms	5624 KB	Output is correct
6	Correct	8 ms	5624 KB	Output is correct
7	Correct	8 ms	5624 KB	Output is correct
8	Correct	9 ms	5624 KB	Output is correct
9	Correct	9 ms	5624 KB	Output is correct
10	Correct	9 ms	5624 KB	Output is correct
11	Correct	9 ms	5624 KB	Output is correct
12	Correct	9 ms	5624 KB	Output is correct
13	Correct	9 ms	5624 KB	Output is correct
14	Correct	9 ms	5624 KB	Output is correct
15	Correct	9 ms	5624 KB	Output is correct
16	Correct	9 ms	5624 KB	Output is correct
17	Correct	9 ms	5616 KB	Output is correct
18	Correct	9 ms	5652 KB	Output is correct
19	Correct	9 ms	5624 KB	Output is correct
20	Correct	262 ms	8308 KB	Output is correct
21	Correct	265 ms	8312 KB	Output is correct
22	Correct	253 ms	8312 KB	Output is correct
23	Correct	259 ms	8408 KB	Output is correct
24	Correct	611 ms	259468 KB	Output is correct
25	Correct	643 ms	259448 KB	Output is correct
26	Correct	597 ms	259260 KB	Output is correct
27	Correct	565 ms	260060 KB	Output is correct
28	Correct	565 ms	259928 KB	Output is correct
29	Correct	558 ms	259976 KB	Output is correct
30	Correct	521 ms	259960 KB	Output is correct
31	Correct	484 ms	259960 KB	Output is correct
32	Correct	496 ms	259832 KB	Output is correct
33	Correct	510 ms	259616 KB	Output is correct
34	Correct	497 ms	259424 KB	Output is correct
35	Correct	536 ms	259364 KB	Output is correct
36	Correct	488 ms	259564 KB	Output is correct
37	Correct	504 ms	259576 KB	Output is correct
38	Correct	507 ms	259440 KB	Output is correct

Subtask #3
0 / 86.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2680 KB	Output is correct
2	Correct	3 ms	2680 KB	Output is correct
3	Correct	3 ms	2680 KB	Output is correct
4	Correct	3 ms	2680 KB	Output is correct
5	Correct	8 ms	5624 KB	Output is correct
6	Correct	8 ms	5624 KB	Output is correct
7	Correct	8 ms	5624 KB	Output is correct
8	Correct	9 ms	5624 KB	Output is correct
9	Correct	9 ms	5624 KB	Output is correct
10	Correct	9 ms	5624 KB	Output is correct
11	Correct	9 ms	5624 KB	Output is correct
12	Correct	9 ms	5624 KB	Output is correct
13	Correct	9 ms	5624 KB	Output is correct
14	Correct	9 ms	5624 KB	Output is correct
15	Correct	9 ms	5624 KB	Output is correct
16	Correct	9 ms	5624 KB	Output is correct
17	Correct	9 ms	5616 KB	Output is correct
18	Correct	9 ms	5652 KB	Output is correct
19	Correct	9 ms	5624 KB	Output is correct
20	Correct	262 ms	8308 KB	Output is correct
21	Correct	265 ms	8312 KB	Output is correct
22	Correct	253 ms	8312 KB	Output is correct
23	Correct	259 ms	8408 KB	Output is correct
24	Correct	611 ms	259468 KB	Output is correct
25	Correct	643 ms	259448 KB	Output is correct
26	Correct	597 ms	259260 KB	Output is correct
27	Correct	565 ms	260060 KB	Output is correct
28	Correct	565 ms	259928 KB	Output is correct
29	Correct	558 ms	259976 KB	Output is correct
30	Correct	521 ms	259960 KB	Output is correct
31	Correct	484 ms	259960 KB	Output is correct
32	Correct	496 ms	259832 KB	Output is correct
33	Correct	510 ms	259616 KB	Output is correct
34	Correct	497 ms	259424 KB	Output is correct
35	Correct	536 ms	259364 KB	Output is correct
36	Correct	488 ms	259564 KB	Output is correct
37	Correct	504 ms	259576 KB	Output is correct
38	Correct	507 ms	259440 KB	Output is correct
39	Correct	697 ms	260272 KB	Output is correct
40	Correct	568 ms	259452 KB	Output is correct
41	Correct	613 ms	259344 KB	Output is correct
42	Correct	613 ms	259736 KB	Output is correct
43	Correct	647 ms	259708 KB	Output is correct
44	Incorrect	321 ms	9256 KB	Output isn't correct
45	Halted	0 ms	0 KB	-

답안 #94445

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 7.0 / 7.0

Subtask #3 0 / 86.0

Subtask #1
7.0 / 7.0

Subtask #2
7.0 / 7.0

Subtask #3
0 / 86.0