답안 #95041 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
95041	2019-01-27T06:59:00 Z	Mahdi_Jfri	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	1170 ms	480248 KB

bitaro

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
typedef vector<pair<int,int>> vii;

const int maxn = 1e5 + 20;
const int sq = 320;

vector<int> in[maxn];
vii path[maxn];

int dp[maxn];

bool is[maxn];

bool cmp(pair<int , int> a , pair<int , int> b)
{
	return a > b;
}

void merge(vii &a , vii &b)
{
	vii c(a.size() + b.size());
	merge(a.begin() , a.end() , b.begin() , b.end() , c.begin() , cmp);
	a = c;

	while(a.size() > sq)
		a.pop_back();
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n , m , q;
	cin >> n >> m >> q;

	for(int i = 0; i < m; i++)
	{
		int a , b;
		cin >> a >> b;
		a-- , b--;
		in[b].pb(a);
	}

	for(int v = 0; v < n; v++)
	{
		path[v].pb({-1 , v});
		for(auto u : in[v])
			merge(path[v] , path[u]);

		for(auto &x : path[v])
			x.first++;
	}

	while(q--)
	{
		int v , sz;
		cin >> v >> sz;
		v--;

		vector<int> tmp(sz);
		for(auto &x : tmp)
			cin >> x , x--;

		for(auto x : tmp)
			is[x] = 1;

		if(sz > sq)
		{
			for(int i = 0; i <= v; i++)
			{
				dp[i] = -1e9;
				if(!is[i])
					dp[i] = 0;
				for(auto u : in[i])
					dp[i] = max(dp[i] , dp[u] + 1);
			}

			dp[v] = max(dp[v] , -1);
			cout << dp[v] << endl;
		}
		else
		{
			bool f = 0;
			for(auto x : path[v])
				if(!is[x.second])
				{
					cout << x.first << endl;
					f = 1;
					break;
				}

			if(!f)
				cout << -1 << endl;
		}

		for(auto x : tmp)
			is[x] = 0;
	}
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	4988 KB	Output is correct
2	Correct	6 ms	5112 KB	Output is correct
3	Correct	5 ms	4988 KB	Output is correct
4	Correct	6 ms	5112 KB	Output is correct
5	Correct	11 ms	7288 KB	Output is correct
6	Correct	11 ms	7032 KB	Output is correct
7	Correct	11 ms	6908 KB	Output is correct
8	Correct	15 ms	9592 KB	Output is correct
9	Correct	15 ms	9720 KB	Output is correct
10	Correct	15 ms	9592 KB	Output is correct
11	Correct	15 ms	9316 KB	Output is correct
12	Correct	12 ms	7544 KB	Output is correct
13	Correct	15 ms	9464 KB	Output is correct
14	Correct	11 ms	7160 KB	Output is correct
15	Correct	9 ms	6008 KB	Output is correct
16	Correct	11 ms	7032 KB	Output is correct
17	Correct	13 ms	8184 KB	Output is correct
18	Correct	10 ms	6648 KB	Output is correct
19	Correct	13 ms	8312 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	4988 KB	Output is correct
2	Correct	6 ms	5112 KB	Output is correct
3	Correct	5 ms	4988 KB	Output is correct
4	Correct	6 ms	5112 KB	Output is correct
5	Correct	11 ms	7288 KB	Output is correct
6	Correct	11 ms	7032 KB	Output is correct
7	Correct	11 ms	6908 KB	Output is correct
8	Correct	15 ms	9592 KB	Output is correct
9	Correct	15 ms	9720 KB	Output is correct
10	Correct	15 ms	9592 KB	Output is correct
11	Correct	15 ms	9316 KB	Output is correct
12	Correct	12 ms	7544 KB	Output is correct
13	Correct	15 ms	9464 KB	Output is correct
14	Correct	11 ms	7160 KB	Output is correct
15	Correct	9 ms	6008 KB	Output is correct
16	Correct	11 ms	7032 KB	Output is correct
17	Correct	13 ms	8184 KB	Output is correct
18	Correct	10 ms	6648 KB	Output is correct
19	Correct	13 ms	8312 KB	Output is correct
20	Correct	471 ms	12788 KB	Output is correct
21	Correct	469 ms	12792 KB	Output is correct
22	Correct	471 ms	12780 KB	Output is correct
23	Correct	488 ms	12680 KB	Output is correct
24	Correct	952 ms	353384 KB	Output is correct
25	Correct	950 ms	352328 KB	Output is correct
26	Correct	791 ms	352520 KB	Output is correct
27	Correct	1112 ms	479548 KB	Output is correct
28	Correct	905 ms	480248 KB	Output is correct
29	Correct	1006 ms	479736 KB	Output is correct
30	Correct	1030 ms	478456 KB	Output is correct
31	Correct	991 ms	451912 KB	Output is correct
32	Correct	969 ms	478888 KB	Output is correct
33	Correct	715 ms	257296 KB	Output is correct
34	Correct	607 ms	205560 KB	Output is correct
35	Correct	601 ms	255608 KB	Output is correct
36	Correct	797 ms	376428 KB	Output is correct
37	Correct	857 ms	327344 KB	Output is correct
38	Correct	831 ms	376536 KB	Output is correct

Subtask #3
0 / 86.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	4988 KB	Output is correct
2	Correct	6 ms	5112 KB	Output is correct
3	Correct	5 ms	4988 KB	Output is correct
4	Correct	6 ms	5112 KB	Output is correct
5	Correct	11 ms	7288 KB	Output is correct
6	Correct	11 ms	7032 KB	Output is correct
7	Correct	11 ms	6908 KB	Output is correct
8	Correct	15 ms	9592 KB	Output is correct
9	Correct	15 ms	9720 KB	Output is correct
10	Correct	15 ms	9592 KB	Output is correct
11	Correct	15 ms	9316 KB	Output is correct
12	Correct	12 ms	7544 KB	Output is correct
13	Correct	15 ms	9464 KB	Output is correct
14	Correct	11 ms	7160 KB	Output is correct
15	Correct	9 ms	6008 KB	Output is correct
16	Correct	11 ms	7032 KB	Output is correct
17	Correct	13 ms	8184 KB	Output is correct
18	Correct	10 ms	6648 KB	Output is correct
19	Correct	13 ms	8312 KB	Output is correct
20	Correct	471 ms	12788 KB	Output is correct
21	Correct	469 ms	12792 KB	Output is correct
22	Correct	471 ms	12780 KB	Output is correct
23	Correct	488 ms	12680 KB	Output is correct
24	Correct	952 ms	353384 KB	Output is correct
25	Correct	950 ms	352328 KB	Output is correct
26	Correct	791 ms	352520 KB	Output is correct
27	Correct	1112 ms	479548 KB	Output is correct
28	Correct	905 ms	480248 KB	Output is correct
29	Correct	1006 ms	479736 KB	Output is correct
30	Correct	1030 ms	478456 KB	Output is correct
31	Correct	991 ms	451912 KB	Output is correct
32	Correct	969 ms	478888 KB	Output is correct
33	Correct	715 ms	257296 KB	Output is correct
34	Correct	607 ms	205560 KB	Output is correct
35	Correct	601 ms	255608 KB	Output is correct
36	Correct	797 ms	376428 KB	Output is correct
37	Correct	857 ms	327344 KB	Output is correct
38	Correct	831 ms	376536 KB	Output is correct
39	Correct	1170 ms	341196 KB	Output is correct
40	Correct	1063 ms	349376 KB	Output is correct
41	Correct	1033 ms	348268 KB	Output is correct
42	Correct	1051 ms	346468 KB	Output is correct
43	Correct	873 ms	346936 KB	Output is correct
44	Incorrect	621 ms	14200 KB	Output isn't correct
45	Halted	0 ms	0 KB	-

답안 #95041

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