#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS
/****Author: Barish Namazov****/
#include <bits/stdc++.h>
using namespace std;
/***TEMPLATE***/
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define F first
#define S second
#define pb push_back
#define endl '\n'
const int max4 = 10004;
const int maxx = 200005;
const int max6 = 1000006;
const int lg5 = 17;
const int INF = 2 * 1000000007;
const long long INFLL = 4LL * 1000000000 * 1000000000;
/***************/
int powmod (int a, int b, int mod) {
int res = 1; a %= mod;
for (; b; b >>= 1) {
if (b & 1) {
res = 1LL * res * a % mod;
}
a = 1LL * a * a % mod;
}
return res;
}
int gcd (int a, int b) {
while (b > 0) {
int t = a % b;
a = b, b = t;
}
return a;
}
int lcm (int a, int b) {
return (a / gcd (a, b)) * b;
}
int is_prime (int n) {
if (n <= 1 || n > 3 && (n % 2 == 0 || n % 3 == 0))
return 0;
for (int i = 5, t = 2; i * i <= n; i += t, t = 6 - t)
if (n % i == 0)
return 0;
return 1;
}
/******Don't forget to use long long when needed!!******/
const int Block = 220;
int n, m, q;
vector <int> g[maxx];
vector <pair <int, int>> dp[maxx]; int res[maxx];
inline void update(int u, int v) {
for (auto i : dp[u]) {
res[i.S] = i.F;
}
for (auto i : dp[v]) {
res[i.S] = max(res[i.S], i.F + 1);
}
for (auto &i : dp[u]) {
i.F = max(i.F, res[i.S]); res[i.S] = 0;
}
vector <pair <int, int>> A, B;
for (auto i : dp[u]) B.pb(i);
for (auto i : dp[v]) {
if (res[i.S] > 0) {
A.pb({i.F + 1, i.S}); res[i.S] = 0;
}
} //sort(rall(A)); sort(rall(B));
while (!dp[u].empty()) dp[u].pop_back();
int ptr1 = 0, ptr2 = 0;
while (ptr1 < A.size() && ptr2 < B.size()) {
if (A[ptr1] > B[ptr2]) {
dp[u].pb(A[ptr1++]);
} else {
dp[u].pb(B[ptr2++]);
}
}
while (ptr1 < A.size()) dp[u].pb(A[ptr1++]);
while (ptr2 < B.size()) dp[u].pb(B[ptr2++]);
while (dp[u].size() > Block) {
dp[u].pop_back();
}
}
int has[maxx], lpath[maxx];
int main() {
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
ios_base :: sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> q;
int a, b;
for (int i = 1; i <= m; i++) {
cin >> a >> b;
g[b].pb(a);
}
for (int i = 1; i <= n; i++) {
for (int j : g[i]) {
update(i, j);
}
if (dp[i].size() < Block) {
dp[i].pb({0, i});
}
}
vector <int> bad; int tmp;
int t, y;
while (q --) {
cin >> t >> y;
for (int i = 0; i < y; i++) {
cin >> tmp;
bad.pb(tmp); has[tmp] = 1;
}
if (y < Block) {
int res = -1;
for (auto i : dp[t]) {
if (has[i.S] == 0) {
res = i.F; break;
}
}
cout << res << endl;
} else {
for (int i = 1; i <= t; i++) {
lpath[i] = -has[i];
for (int j : g[i]) {
if (lpath[j] != -1) {
lpath[i] = max(lpath[i], lpath[j] + 1);
}
}
}
cout << lpath[t] << endl;
}
for (int i = 0; i < y; i++) {
has[bad[i]] = 0;
}
bad.clear();
}
return 0;
}
Compilation message
bitaro.cpp:1:0: warning: ignoring #pragma comment [-Wunknown-pragmas]
#pragma comment(linker, "/stack:200000000")
bitaro.cpp: In function 'int is_prime(int)':
bitaro.cpp:55:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if (n <= 1 || n > 3 && (n % 2 == 0 || n % 3 == 0))
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'void update(int, int)':
bitaro.cpp:90:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (ptr1 < A.size() && ptr2 < B.size()) {
~~~~~^~~~~~~~~~
bitaro.cpp:90:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (ptr1 < A.size() && ptr2 < B.size()) {
~~~~~^~~~~~~~~~
bitaro.cpp:97:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (ptr1 < A.size()) dp[u].pb(A[ptr1++]);
~~~~~^~~~~~~~~~
bitaro.cpp:98:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (ptr2 < B.size()) dp[u].pb(B[ptr2++]);
~~~~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
9692 KB |
Output is correct |
2 |
Correct |
11 ms |
9720 KB |
Output is correct |
3 |
Correct |
11 ms |
9720 KB |
Output is correct |
4 |
Correct |
9 ms |
9720 KB |
Output is correct |
5 |
Correct |
14 ms |
10232 KB |
Output is correct |
6 |
Correct |
13 ms |
10232 KB |
Output is correct |
7 |
Correct |
23 ms |
10232 KB |
Output is correct |
8 |
Correct |
18 ms |
11512 KB |
Output is correct |
9 |
Correct |
18 ms |
11640 KB |
Output is correct |
10 |
Correct |
17 ms |
11772 KB |
Output is correct |
11 |
Correct |
17 ms |
11512 KB |
Output is correct |
12 |
Correct |
17 ms |
11000 KB |
Output is correct |
13 |
Correct |
18 ms |
11512 KB |
Output is correct |
14 |
Correct |
18 ms |
10872 KB |
Output is correct |
15 |
Correct |
15 ms |
10616 KB |
Output is correct |
16 |
Correct |
18 ms |
10872 KB |
Output is correct |
17 |
Correct |
19 ms |
11132 KB |
Output is correct |
18 |
Correct |
15 ms |
10744 KB |
Output is correct |
19 |
Correct |
17 ms |
11128 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
9692 KB |
Output is correct |
2 |
Correct |
11 ms |
9720 KB |
Output is correct |
3 |
Correct |
11 ms |
9720 KB |
Output is correct |
4 |
Correct |
9 ms |
9720 KB |
Output is correct |
5 |
Correct |
14 ms |
10232 KB |
Output is correct |
6 |
Correct |
13 ms |
10232 KB |
Output is correct |
7 |
Correct |
23 ms |
10232 KB |
Output is correct |
8 |
Correct |
18 ms |
11512 KB |
Output is correct |
9 |
Correct |
18 ms |
11640 KB |
Output is correct |
10 |
Correct |
17 ms |
11772 KB |
Output is correct |
11 |
Correct |
17 ms |
11512 KB |
Output is correct |
12 |
Correct |
17 ms |
11000 KB |
Output is correct |
13 |
Correct |
18 ms |
11512 KB |
Output is correct |
14 |
Correct |
18 ms |
10872 KB |
Output is correct |
15 |
Correct |
15 ms |
10616 KB |
Output is correct |
16 |
Correct |
18 ms |
10872 KB |
Output is correct |
17 |
Correct |
19 ms |
11132 KB |
Output is correct |
18 |
Correct |
15 ms |
10744 KB |
Output is correct |
19 |
Correct |
17 ms |
11128 KB |
Output is correct |
20 |
Correct |
517 ms |
14112 KB |
Output is correct |
21 |
Correct |
511 ms |
14072 KB |
Output is correct |
22 |
Correct |
515 ms |
14096 KB |
Output is correct |
23 |
Correct |
538 ms |
14148 KB |
Output is correct |
24 |
Correct |
1171 ms |
217460 KB |
Output is correct |
25 |
Correct |
1250 ms |
225464 KB |
Output is correct |
26 |
Correct |
1359 ms |
225372 KB |
Output is correct |
27 |
Correct |
976 ms |
218228 KB |
Output is correct |
28 |
Correct |
903 ms |
218240 KB |
Output is correct |
29 |
Correct |
924 ms |
218024 KB |
Output is correct |
30 |
Correct |
922 ms |
217824 KB |
Output is correct |
31 |
Correct |
1326 ms |
325828 KB |
Output is correct |
32 |
Correct |
984 ms |
217752 KB |
Output is correct |
33 |
Correct |
768 ms |
142768 KB |
Output is correct |
34 |
Correct |
965 ms |
175396 KB |
Output is correct |
35 |
Correct |
769 ms |
142176 KB |
Output is correct |
36 |
Correct |
910 ms |
179808 KB |
Output is correct |
37 |
Correct |
1247 ms |
249316 KB |
Output is correct |
38 |
Correct |
879 ms |
179968 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
9692 KB |
Output is correct |
2 |
Correct |
11 ms |
9720 KB |
Output is correct |
3 |
Correct |
11 ms |
9720 KB |
Output is correct |
4 |
Correct |
9 ms |
9720 KB |
Output is correct |
5 |
Correct |
14 ms |
10232 KB |
Output is correct |
6 |
Correct |
13 ms |
10232 KB |
Output is correct |
7 |
Correct |
23 ms |
10232 KB |
Output is correct |
8 |
Correct |
18 ms |
11512 KB |
Output is correct |
9 |
Correct |
18 ms |
11640 KB |
Output is correct |
10 |
Correct |
17 ms |
11772 KB |
Output is correct |
11 |
Correct |
17 ms |
11512 KB |
Output is correct |
12 |
Correct |
17 ms |
11000 KB |
Output is correct |
13 |
Correct |
18 ms |
11512 KB |
Output is correct |
14 |
Correct |
18 ms |
10872 KB |
Output is correct |
15 |
Correct |
15 ms |
10616 KB |
Output is correct |
16 |
Correct |
18 ms |
10872 KB |
Output is correct |
17 |
Correct |
19 ms |
11132 KB |
Output is correct |
18 |
Correct |
15 ms |
10744 KB |
Output is correct |
19 |
Correct |
17 ms |
11128 KB |
Output is correct |
20 |
Correct |
517 ms |
14112 KB |
Output is correct |
21 |
Correct |
511 ms |
14072 KB |
Output is correct |
22 |
Correct |
515 ms |
14096 KB |
Output is correct |
23 |
Correct |
538 ms |
14148 KB |
Output is correct |
24 |
Correct |
1171 ms |
217460 KB |
Output is correct |
25 |
Correct |
1250 ms |
225464 KB |
Output is correct |
26 |
Correct |
1359 ms |
225372 KB |
Output is correct |
27 |
Correct |
976 ms |
218228 KB |
Output is correct |
28 |
Correct |
903 ms |
218240 KB |
Output is correct |
29 |
Correct |
924 ms |
218024 KB |
Output is correct |
30 |
Correct |
922 ms |
217824 KB |
Output is correct |
31 |
Correct |
1326 ms |
325828 KB |
Output is correct |
32 |
Correct |
984 ms |
217752 KB |
Output is correct |
33 |
Correct |
768 ms |
142768 KB |
Output is correct |
34 |
Correct |
965 ms |
175396 KB |
Output is correct |
35 |
Correct |
769 ms |
142176 KB |
Output is correct |
36 |
Correct |
910 ms |
179808 KB |
Output is correct |
37 |
Correct |
1247 ms |
249316 KB |
Output is correct |
38 |
Correct |
879 ms |
179968 KB |
Output is correct |
39 |
Incorrect |
1515 ms |
221544 KB |
Output isn't correct |
40 |
Halted |
0 ms |
0 KB |
- |