oj.uz

Submission #95066

# Submission time Handle Problem Language Result Execution time Memory
95066 2019-01-27T07:37:42 Z ckodser Bitaro’s Party (JOI18_bitaro) C++14
100 / 100
 1506 ms 420728 KB 
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
using namespace std;
const int N = 100745, SQ = 300;
int n, m, q, dp[N], M[N], mark[N];
vector < int > in[N], out[N];
vector < pair < int , int > > best[N];
inline int Brute(int v, vector < int > vec)
{
	memset(M, 0, sizeof(M));
	memset(dp, -63, sizeof(dp));
	dp[v] = 0;
	for (int i = v - 1; i; i--)
		for (int &u : out[i])
			if (u <= v)
				dp[i] = max(dp[i], dp[u] + 1);
	for (int u : vec)
		M[u] = 1;
	int Mx = -1;
	for (int i = 1; i <= v; i++)
		if (M[i] == 0)
			Mx = max(Mx, dp[i]);
	return (Mx);
}
int main()
{
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 1; i <= m; i++)
	{
		int v, u;
		scanf("%d%d", &v, &u);
		out[v].pb(u);
		in[u].pb(v);
	}

	for (int v = 1; v <= n; v++)
	{
		in[v].pb(0);
		best[0] = {{-1, v}};

		int d = (int)in[v].size();

		vector < int > ptr(d, 0);

		while ((int)best[v].size() < SQ)
		{
			int id = -1;
			pair < int , int > Mx = {-1, -1};
			for (int i = 0; i < d; i++)
			{
				int &u = in[v][i];
				while (ptr[i] < (int)best[u].size() && mark[best[u][ptr[i]].second] == v)
					ptr[i] ++;

				if (ptr[i] == (int)best[u].size())
					continue;

				if (Mx.first < best[u][ptr[i]].first + 1)
				{
					Mx = best[u][ptr[i]];
					Mx.first ++;
					id = i;
				}
			}
			if (id == -1)
				break;

			mark[Mx.second] = v;
			ptr[id] ++;
			best[v].pb(Mx);
		}
	}

	memset(mark, 0, sizeof(mark));
	for (int ts = 1; ts <= q; ts ++)
	{
		int v, len;
		vector < int > vec;
		scanf("%d%d", &v, &len);
		vec.resize(len);
		for (int i = 0; i < len; i++)
		{
			scanf("%d", &vec[i]);
			mark[vec[i]] = ts;
		}

		if (vec.size() >= SQ - 10)
		{
			printf("%d\n", Brute(v, vec));
			continue;
		}

		int Mx = -1;
		for (auto X : best[v])
			if (mark[X.second] < ts)
				Mx = max(Mx, X.first);
		printf("%d\n", Mx);
	}
	return 0;
}

Compilation message

bitaro.cpp: In function 'int main()':
bitaro.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &v, &u);
   ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &v, &len);
   ~~~~~^~~~~~~~~~~~~~~~~~
bitaro.cpp:85:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &vec[i]);
    ~~~~~^~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7800 KB Output is correct
2 Correct 8 ms 7804 KB Output is correct
3 Correct 9 ms 7800 KB Output is correct
4 Correct 9 ms 7800 KB Output is correct
5 Correct 12 ms 9080 KB Output is correct
6 Correct 12 ms 9084 KB Output is correct
7 Correct 13 ms 9084 KB Output is correct
8 Correct 17 ms 12024 KB Output is correct
9 Correct 18 ms 12024 KB Output is correct
10 Correct 17 ms 12024 KB Output is correct
11 Correct 17 ms 11640 KB Output is correct
12 Correct 13 ms 9976 KB Output is correct
13 Correct 16 ms 11384 KB Output is correct
14 Correct 15 ms 10616 KB Output is correct
15 Correct 13 ms 9592 KB Output is correct
16 Correct 14 ms 10620 KB Output is correct
17 Correct 15 ms 10872 KB Output is correct
18 Correct 14 ms 9848 KB Output is correct
19 Correct 16 ms 10872 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7800 KB Output is correct
2 Correct 8 ms 7804 KB Output is correct
3 Correct 9 ms 7800 KB Output is correct
4 Correct 9 ms 7800 KB Output is correct
5 Correct 12 ms 9080 KB Output is correct
6 Correct 12 ms 9084 KB Output is correct
7 Correct 13 ms 9084 KB Output is correct
8 Correct 17 ms 12024 KB Output is correct
9 Correct 18 ms 12024 KB Output is correct
10 Correct 17 ms 12024 KB Output is correct
11 Correct 17 ms 11640 KB Output is correct
12 Correct 13 ms 9976 KB Output is correct
13 Correct 16 ms 11384 KB Output is correct
14 Correct 15 ms 10616 KB Output is correct
15 Correct 13 ms 9592 KB Output is correct
16 Correct 14 ms 10620 KB Output is correct
17 Correct 15 ms 10872 KB Output is correct
18 Correct 14 ms 9848 KB Output is correct
19 Correct 16 ms 10872 KB Output is correct
20 Correct 433 ms 15656 KB Output is correct
21 Correct 437 ms 15592 KB Output is correct
22 Correct 460 ms 15612 KB Output is correct
23 Correct 468 ms 15760 KB Output is correct
24 Correct 891 ms 259528 KB Output is correct
25 Correct 1126 ms 271064 KB Output is correct
26 Correct 1098 ms 270384 KB Output is correct
27 Correct 1144 ms 420012 KB Output is correct
28 Correct 1247 ms 420176 KB Output is correct
29 Correct 1196 ms 418880 KB Output is correct
30 Correct 1243 ms 418204 KB Output is correct
31 Correct 1231 ms 404320 KB Output is correct
32 Correct 1175 ms 418988 KB Output is correct
33 Correct 811 ms 262344 KB Output is correct
34 Correct 667 ms 216056 KB Output is correct
35 Correct 751 ms 260476 KB Output is correct
36 Correct 933 ms 340340 KB Output is correct
37 Correct 971 ms 308652 KB Output is correct
38 Correct 963 ms 341368 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7800 KB Output is correct
2 Correct 8 ms 7804 KB Output is correct
3 Correct 9 ms 7800 KB Output is correct
4 Correct 9 ms 7800 KB Output is correct
5 Correct 12 ms 9080 KB Output is correct
6 Correct 12 ms 9084 KB Output is correct
7 Correct 13 ms 9084 KB Output is correct
8 Correct 17 ms 12024 KB Output is correct
9 Correct 18 ms 12024 KB Output is correct
10 Correct 17 ms 12024 KB Output is correct
11 Correct 17 ms 11640 KB Output is correct
12 Correct 13 ms 9976 KB Output is correct
13 Correct 16 ms 11384 KB Output is correct
14 Correct 15 ms 10616 KB Output is correct
15 Correct 13 ms 9592 KB Output is correct
16 Correct 14 ms 10620 KB Output is correct
17 Correct 15 ms 10872 KB Output is correct
18 Correct 14 ms 9848 KB Output is correct
19 Correct 16 ms 10872 KB Output is correct
20 Correct 433 ms 15656 KB Output is correct
21 Correct 437 ms 15592 KB Output is correct
22 Correct 460 ms 15612 KB Output is correct
23 Correct 468 ms 15760 KB Output is correct
24 Correct 891 ms 259528 KB Output is correct
25 Correct 1126 ms 271064 KB Output is correct
26 Correct 1098 ms 270384 KB Output is correct
27 Correct 1144 ms 420012 KB Output is correct
28 Correct 1247 ms 420176 KB Output is correct
29 Correct 1196 ms 418880 KB Output is correct
30 Correct 1243 ms 418204 KB Output is correct
31 Correct 1231 ms 404320 KB Output is correct
32 Correct 1175 ms 418988 KB Output is correct
33 Correct 811 ms 262344 KB Output is correct
34 Correct 667 ms 216056 KB Output is correct
35 Correct 751 ms 260476 KB Output is correct
36 Correct 933 ms 340340 KB Output is correct
37 Correct 971 ms 308652 KB Output is correct
38 Correct 963 ms 341368 KB Output is correct
39 Correct 1140 ms 260984 KB Output is correct
40 Correct 1068 ms 263288 KB Output is correct
41 Correct 1122 ms 265480 KB Output is correct
42 Correct 1082 ms 263328 KB Output is correct
43 Correct 1135 ms 262908 KB Output is correct
44 Correct 518 ms 13820 KB Output is correct
45 Correct 436 ms 13560 KB Output is correct
46 Correct 430 ms 13560 KB Output is correct
47 Correct 484 ms 14296 KB Output is correct
48 Correct 441 ms 14456 KB Output is correct
49 Correct 1297 ms 417020 KB Output is correct
50 Correct 1226 ms 418936 KB Output is correct
51 Correct 478 ms 16088 KB Output is correct
52 Correct 440 ms 15352 KB Output is correct
53 Correct 1192 ms 339576 KB Output is correct
54 Correct 1129 ms 309624 KB Output is correct
55 Correct 937 ms 339060 KB Output is correct
56 Correct 988 ms 309496 KB Output is correct
57 Correct 494 ms 16164 KB Output is correct
58 Correct 493 ms 16248 KB Output is correct
59 Correct 428 ms 15224 KB Output is correct
60 Correct 451 ms 15352 KB Output is correct
61 Correct 1159 ms 419960 KB Output is correct
62 Correct 1101 ms 341276 KB Output is correct
63 Correct 1191 ms 308692 KB Output is correct
64 Correct 1506 ms 419832 KB Output is correct
65 Correct 1261 ms 339576 KB Output is correct
66 Correct 1217 ms 310392 KB Output is correct
67 Correct 1201 ms 419064 KB Output is correct
68 Correct 1026 ms 340472 KB Output is correct
69 Correct 972 ms 305864 KB Output is correct
70 Correct 1180 ms 420088 KB Output is correct
71 Correct 1054 ms 341404 KB Output is correct
72 Correct 1008 ms 310008 KB Output is correct
73 Correct 1195 ms 420020 KB Output is correct
74 Correct 924 ms 341240 KB Output is correct
75 Correct 1038 ms 310136 KB Output is correct
76 Correct 1388 ms 420728 KB Output is correct
77 Correct 1106 ms 419288 KB Output is correct
78 Correct 1128 ms 420156 KB Output is correct
79 Correct 509 ms 16204 KB Output is correct
80 Correct 427 ms 15480 KB Output is correct
81 Correct 421 ms 15736 KB Output is correct
82 Correct 1373 ms 419324 KB Output is correct
83 Correct 1222 ms 404856 KB Output is correct
84 Correct 1055 ms 418040 KB Output is correct
85 Correct 1014 ms 403208 KB Output is correct
86 Correct 1094 ms 419048 KB Output is correct
87 Correct 1143 ms 405116 KB Output is correct
88 Correct 480 ms 16264 KB Output is correct
89 Correct 467 ms 16504 KB Output is correct
90 Correct 420 ms 15480 KB Output is correct
91 Correct 440 ms 15380 KB Output is correct
92 Correct 418 ms 15756 KB Output is correct
93 Correct 456 ms 15864 KB Output is correct
94 Correct 955 ms 262912 KB Output is correct
95 Correct 745 ms 215400 KB Output is correct
96 Correct 771 ms 260344 KB Output is correct
97 Correct 702 ms 218336 KB Output is correct
98 Correct 779 ms 262136 KB Output is correct
99 Correct 759 ms 218588 KB Output is correct
100 Correct 512 ms 16376 KB Output is correct
101 Correct 524 ms 16396 KB Output is correct
102 Correct 514 ms 15564 KB Output is correct
103 Correct 470 ms 15480 KB Output is correct
104 Correct 466 ms 15900 KB Output is correct
105 Correct 469 ms 15964 KB Output is correct
106 Correct 1140 ms 340324 KB Output is correct
107 Correct 1053 ms 310260 KB Output is correct
108 Correct 893 ms 341264 KB Output is correct
109 Correct 937 ms 308632 KB Output is correct
110 Correct 908 ms 342360 KB Output is correct
111 Correct 950 ms 310728 KB Output is correct
112 Correct 487 ms 16504 KB Output is correct
113 Correct 518 ms 16376 KB Output is correct
114 Correct 450 ms 15352 KB Output is correct
115 Correct 436 ms 15404 KB Output is correct
116 Correct 425 ms 15800 KB Output is correct
117 Correct 441 ms 15892 KB Output is correct
118 Correct 1123 ms 418992 KB Output is correct
119 Correct 1054 ms 341112 KB Output is correct
120 Correct 991 ms 308344 KB Output is correct
121 Correct 1164 ms 419040 KB Output is correct
122 Correct 1040 ms 339624 KB Output is correct
123 Correct 964 ms 308600 KB Output is correct
124 Correct 1173 ms 419064 KB Output is correct
125 Correct 954 ms 341264 KB Output is correct
126 Correct 978 ms 307336 KB Output is correct