#define _FORTIFY_SOURCE 0
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
constexpr int maxn = 1e5 + 10;
int n, m, q, grau2[maxn];
int dp[maxn];
vector<int> grafo[maxn], g[maxn];
bool mark[maxn], mark2[maxn], tem[maxn];
vector<pii> guarda[maxn];
#define gc getchar_unlocked
inline int scan() {
int x = gc(), n = 0;
for(;x < '0' || x > '9'; x = gc()) {}
for(;x >= '0' && x <= '9'; x = gc()) n = 10*n + x - '0';
return n;
}
int dfs_dp(int u) {
if(dp[u] != -1) return dp[u];
tem[u] = !mark[u];
int& ans = dp[u];
ans = 0;
for(int v : g[u])
ans = max(ans, dfs_dp(v)+tem[v]), tem[u] |= tem[v];
return ans;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
n = scan(), m = scan(), q = scan();
int sq = 200;
for (int i = 1; i <= m; i++) {
int a, b;
a = scan(), b = scan();
grafo[a].push_back(b);
g[b].push_back(a);
grau2[b]++;
}
{ // precompute unordered map
queue<int> fila;
for (int i = 1; i <= n; i++) {
guarda[i].push_back({0, i});
if (grau2[i] == 0) fila.push(i);
guarda[i].reserve(sq+1);
}
vector<pii> aux;
aux.reserve(2*sq);
while (!fila.empty()) {
int u = fila.front();
fila.pop();
for(auto& e : guarda[u])
e.first++;
for(auto v : grafo[u]) {
aux.resize(guarda[u].size() + guarda[v].size());
grau2[v]--;
if (grau2[v] == 0) fila.push(v);
merge(guarda[u].begin(), guarda[u].end(),
guarda[v].begin(), guarda[v].end(), aux.begin(), greater<pii>());
guarda[v].clear();
for(auto it = aux.begin(); it != aux.end() && guarda[v].size() <= sq; it++)
if(!mark[it->second]) guarda[v].push_back(*it), mark[it->second] = true;
for (auto e : guarda[v])
mark[e.second] = false;
}
for (auto& e : guarda[u])
e.first--;
}
}
for (int i = 1; i <= q; i++) {
int t, y;
t = scan(), y= scan();
vector<int> query(y);
for (int i = 0; i < y; i++)
query[i] = scan();
if (y >= sq) {
memset(dp, -1, sizeof dp);
for (int i = 0; i < y; i++)
mark[query[i]] = true;
cout << (dfs_dp(t)==0&&mark[t]?-1:dp[t]) << '\n';
for (int i = 0; i < y; i++)
mark[query[i]] = false;
} else {
for (int j = 0; j < y; j++)
mark2[query[j]] = true;
int ans = -1;
for (auto it = guarda[t].begin(); it != guarda[t].end(); it++) {
if (!mark2[it->second]) {
ans = it->first;
break;
}
}
for (int j = 0; j < y; j++)
mark2[query[j]] = false;
cout << ans << '\n';
}
}
return 0;
}
Compilation message
bitaro.cpp:1: warning: "_FORTIFY_SOURCE" redefined
1 | #define _FORTIFY_SOURCE 0
|
<built-in>: note: this is the location of the previous definition
bitaro.cpp:25:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
25 | #pragma GCC optimize("-fwhole-program")
| ^
bitaro.cpp:32:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
32 | #pragma GCC optimize("-fstrict-overflow")
| ^
bitaro.cpp:34:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
34 | #pragma GCC optimize("-fcse-skip-blocks")
| ^
bitaro.cpp:48:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
48 | #pragma GCC optimize("-funsafe-loop-optimizations")
| ^
bitaro.cpp:63:17: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
63 | inline int scan() {
| ^
bitaro.cpp:63:17: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
bitaro.cpp:63:17: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
bitaro.cpp:63:17: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
bitaro.cpp:70:17: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
70 | int dfs_dp(int u) {
| ^
bitaro.cpp:70:17: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
bitaro.cpp:70:17: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
bitaro.cpp:70:17: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
bitaro.cpp:80:10: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
80 | int main() {
| ^
bitaro.cpp:80:10: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
bitaro.cpp:80:10: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
bitaro.cpp:80:10: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
bitaro.cpp: In function 'int main()':
bitaro.cpp:118:68: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
118 | for(auto it = aux.begin(); it != aux.end() && guarda[v].size() <= sq; it++)
| ~~~~~~~~~~~~~~~~~^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
7404 KB |
Output is correct |
2 |
Correct |
6 ms |
7404 KB |
Output is correct |
3 |
Correct |
6 ms |
7404 KB |
Output is correct |
4 |
Correct |
6 ms |
7404 KB |
Output is correct |
5 |
Correct |
9 ms |
9452 KB |
Output is correct |
6 |
Correct |
9 ms |
9452 KB |
Output is correct |
7 |
Correct |
8 ms |
9452 KB |
Output is correct |
8 |
Correct |
11 ms |
9452 KB |
Output is correct |
9 |
Correct |
11 ms |
9452 KB |
Output is correct |
10 |
Correct |
11 ms |
9452 KB |
Output is correct |
11 |
Correct |
12 ms |
9452 KB |
Output is correct |
12 |
Correct |
10 ms |
9452 KB |
Output is correct |
13 |
Correct |
13 ms |
9452 KB |
Output is correct |
14 |
Correct |
11 ms |
9452 KB |
Output is correct |
15 |
Correct |
10 ms |
9452 KB |
Output is correct |
16 |
Correct |
10 ms |
9452 KB |
Output is correct |
17 |
Correct |
11 ms |
9452 KB |
Output is correct |
18 |
Correct |
10 ms |
9452 KB |
Output is correct |
19 |
Correct |
12 ms |
9452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
7404 KB |
Output is correct |
2 |
Correct |
6 ms |
7404 KB |
Output is correct |
3 |
Correct |
6 ms |
7404 KB |
Output is correct |
4 |
Correct |
6 ms |
7404 KB |
Output is correct |
5 |
Correct |
9 ms |
9452 KB |
Output is correct |
6 |
Correct |
9 ms |
9452 KB |
Output is correct |
7 |
Correct |
8 ms |
9452 KB |
Output is correct |
8 |
Correct |
11 ms |
9452 KB |
Output is correct |
9 |
Correct |
11 ms |
9452 KB |
Output is correct |
10 |
Correct |
11 ms |
9452 KB |
Output is correct |
11 |
Correct |
12 ms |
9452 KB |
Output is correct |
12 |
Correct |
10 ms |
9452 KB |
Output is correct |
13 |
Correct |
13 ms |
9452 KB |
Output is correct |
14 |
Correct |
11 ms |
9452 KB |
Output is correct |
15 |
Correct |
10 ms |
9452 KB |
Output is correct |
16 |
Correct |
10 ms |
9452 KB |
Output is correct |
17 |
Correct |
11 ms |
9452 KB |
Output is correct |
18 |
Correct |
10 ms |
9452 KB |
Output is correct |
19 |
Correct |
12 ms |
9452 KB |
Output is correct |
20 |
Correct |
394 ms |
12012 KB |
Output is correct |
21 |
Correct |
367 ms |
11904 KB |
Output is correct |
22 |
Correct |
389 ms |
12012 KB |
Output is correct |
23 |
Correct |
477 ms |
12012 KB |
Output is correct |
24 |
Correct |
680 ms |
171884 KB |
Output is correct |
25 |
Correct |
728 ms |
171884 KB |
Output is correct |
26 |
Correct |
728 ms |
172140 KB |
Output is correct |
27 |
Correct |
669 ms |
176876 KB |
Output is correct |
28 |
Correct |
680 ms |
177132 KB |
Output is correct |
29 |
Correct |
681 ms |
178540 KB |
Output is correct |
30 |
Correct |
685 ms |
172524 KB |
Output is correct |
31 |
Correct |
721 ms |
172524 KB |
Output is correct |
32 |
Correct |
690 ms |
172784 KB |
Output is correct |
33 |
Correct |
524 ms |
172576 KB |
Output is correct |
34 |
Correct |
503 ms |
172652 KB |
Output is correct |
35 |
Correct |
510 ms |
172652 KB |
Output is correct |
36 |
Correct |
609 ms |
172908 KB |
Output is correct |
37 |
Correct |
647 ms |
172780 KB |
Output is correct |
38 |
Correct |
611 ms |
172780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
7404 KB |
Output is correct |
2 |
Correct |
6 ms |
7404 KB |
Output is correct |
3 |
Correct |
6 ms |
7404 KB |
Output is correct |
4 |
Correct |
6 ms |
7404 KB |
Output is correct |
5 |
Correct |
9 ms |
9452 KB |
Output is correct |
6 |
Correct |
9 ms |
9452 KB |
Output is correct |
7 |
Correct |
8 ms |
9452 KB |
Output is correct |
8 |
Correct |
11 ms |
9452 KB |
Output is correct |
9 |
Correct |
11 ms |
9452 KB |
Output is correct |
10 |
Correct |
11 ms |
9452 KB |
Output is correct |
11 |
Correct |
12 ms |
9452 KB |
Output is correct |
12 |
Correct |
10 ms |
9452 KB |
Output is correct |
13 |
Correct |
13 ms |
9452 KB |
Output is correct |
14 |
Correct |
11 ms |
9452 KB |
Output is correct |
15 |
Correct |
10 ms |
9452 KB |
Output is correct |
16 |
Correct |
10 ms |
9452 KB |
Output is correct |
17 |
Correct |
11 ms |
9452 KB |
Output is correct |
18 |
Correct |
10 ms |
9452 KB |
Output is correct |
19 |
Correct |
12 ms |
9452 KB |
Output is correct |
20 |
Correct |
394 ms |
12012 KB |
Output is correct |
21 |
Correct |
367 ms |
11904 KB |
Output is correct |
22 |
Correct |
389 ms |
12012 KB |
Output is correct |
23 |
Correct |
477 ms |
12012 KB |
Output is correct |
24 |
Correct |
680 ms |
171884 KB |
Output is correct |
25 |
Correct |
728 ms |
171884 KB |
Output is correct |
26 |
Correct |
728 ms |
172140 KB |
Output is correct |
27 |
Correct |
669 ms |
176876 KB |
Output is correct |
28 |
Correct |
680 ms |
177132 KB |
Output is correct |
29 |
Correct |
681 ms |
178540 KB |
Output is correct |
30 |
Correct |
685 ms |
172524 KB |
Output is correct |
31 |
Correct |
721 ms |
172524 KB |
Output is correct |
32 |
Correct |
690 ms |
172784 KB |
Output is correct |
33 |
Correct |
524 ms |
172576 KB |
Output is correct |
34 |
Correct |
503 ms |
172652 KB |
Output is correct |
35 |
Correct |
510 ms |
172652 KB |
Output is correct |
36 |
Correct |
609 ms |
172908 KB |
Output is correct |
37 |
Correct |
647 ms |
172780 KB |
Output is correct |
38 |
Correct |
611 ms |
172780 KB |
Output is correct |
39 |
Correct |
757 ms |
171756 KB |
Output is correct |
40 |
Correct |
740 ms |
171500 KB |
Output is correct |
41 |
Correct |
700 ms |
171352 KB |
Output is correct |
42 |
Correct |
722 ms |
171756 KB |
Output is correct |
43 |
Correct |
716 ms |
171884 KB |
Output is correct |
44 |
Correct |
413 ms |
11884 KB |
Output is correct |
45 |
Correct |
392 ms |
12524 KB |
Output is correct |
46 |
Correct |
402 ms |
12400 KB |
Output is correct |
47 |
Correct |
415 ms |
12524 KB |
Output is correct |
48 |
Correct |
382 ms |
12524 KB |
Output is correct |
49 |
Correct |
721 ms |
174292 KB |
Output is correct |
50 |
Correct |
665 ms |
173548 KB |
Output is correct |
51 |
Correct |
385 ms |
12908 KB |
Output is correct |
52 |
Correct |
369 ms |
12268 KB |
Output is correct |
53 |
Correct |
692 ms |
173800 KB |
Output is correct |
54 |
Correct |
668 ms |
173548 KB |
Output is correct |
55 |
Correct |
658 ms |
173104 KB |
Output is correct |
56 |
Correct |
643 ms |
173036 KB |
Output is correct |
57 |
Correct |
408 ms |
12780 KB |
Output is correct |
58 |
Correct |
418 ms |
12652 KB |
Output is correct |
59 |
Correct |
388 ms |
12268 KB |
Output is correct |
60 |
Correct |
385 ms |
12328 KB |
Output is correct |
61 |
Correct |
1054 ms |
180204 KB |
Output is correct |
62 |
Correct |
831 ms |
173556 KB |
Output is correct |
63 |
Correct |
711 ms |
173504 KB |
Output is correct |
64 |
Correct |
1871 ms |
180208 KB |
Output is correct |
65 |
Correct |
1227 ms |
174316 KB |
Output is correct |
66 |
Correct |
913 ms |
174316 KB |
Output is correct |
67 |
Correct |
1648 ms |
180972 KB |
Output is correct |
68 |
Correct |
1127 ms |
175468 KB |
Output is correct |
69 |
Correct |
875 ms |
175340 KB |
Output is correct |
70 |
Correct |
725 ms |
181356 KB |
Output is correct |
71 |
Correct |
681 ms |
175468 KB |
Output is correct |
72 |
Correct |
652 ms |
175340 KB |
Output is correct |
73 |
Correct |
831 ms |
181908 KB |
Output is correct |
74 |
Correct |
740 ms |
175468 KB |
Output is correct |
75 |
Correct |
685 ms |
175340 KB |
Output is correct |
76 |
Correct |
708 ms |
176492 KB |
Output is correct |
77 |
Correct |
766 ms |
181996 KB |
Output is correct |
78 |
Correct |
708 ms |
181740 KB |
Output is correct |
79 |
Correct |
384 ms |
14444 KB |
Output is correct |
80 |
Correct |
373 ms |
13932 KB |
Output is correct |
81 |
Correct |
375 ms |
13548 KB |
Output is correct |
82 |
Correct |
719 ms |
175468 KB |
Output is correct |
83 |
Correct |
758 ms |
175212 KB |
Output is correct |
84 |
Correct |
788 ms |
176492 KB |
Output is correct |
85 |
Correct |
763 ms |
175468 KB |
Output is correct |
86 |
Correct |
714 ms |
176092 KB |
Output is correct |
87 |
Correct |
746 ms |
175212 KB |
Output is correct |
88 |
Correct |
414 ms |
14316 KB |
Output is correct |
89 |
Correct |
406 ms |
14500 KB |
Output is correct |
90 |
Correct |
407 ms |
13860 KB |
Output is correct |
91 |
Correct |
407 ms |
13804 KB |
Output is correct |
92 |
Correct |
392 ms |
13548 KB |
Output is correct |
93 |
Correct |
395 ms |
13420 KB |
Output is correct |
94 |
Correct |
560 ms |
175292 KB |
Output is correct |
95 |
Correct |
584 ms |
175192 KB |
Output is correct |
96 |
Correct |
606 ms |
175468 KB |
Output is correct |
97 |
Correct |
551 ms |
175212 KB |
Output is correct |
98 |
Correct |
596 ms |
175468 KB |
Output is correct |
99 |
Correct |
553 ms |
175212 KB |
Output is correct |
100 |
Correct |
493 ms |
14444 KB |
Output is correct |
101 |
Correct |
496 ms |
14444 KB |
Output is correct |
102 |
Correct |
470 ms |
13932 KB |
Output is correct |
103 |
Correct |
483 ms |
13876 KB |
Output is correct |
104 |
Correct |
468 ms |
13552 KB |
Output is correct |
105 |
Correct |
479 ms |
13548 KB |
Output is correct |
106 |
Correct |
687 ms |
175212 KB |
Output is correct |
107 |
Correct |
682 ms |
174956 KB |
Output is correct |
108 |
Correct |
674 ms |
175084 KB |
Output is correct |
109 |
Correct |
663 ms |
175212 KB |
Output is correct |
110 |
Correct |
695 ms |
175084 KB |
Output is correct |
111 |
Correct |
659 ms |
174872 KB |
Output is correct |
112 |
Correct |
433 ms |
14188 KB |
Output is correct |
113 |
Correct |
408 ms |
14060 KB |
Output is correct |
114 |
Correct |
411 ms |
13992 KB |
Output is correct |
115 |
Correct |
401 ms |
13932 KB |
Output is correct |
116 |
Correct |
398 ms |
13420 KB |
Output is correct |
117 |
Correct |
395 ms |
13548 KB |
Output is correct |
118 |
Correct |
669 ms |
174688 KB |
Output is correct |
119 |
Correct |
643 ms |
174316 KB |
Output is correct |
120 |
Correct |
660 ms |
174188 KB |
Output is correct |
121 |
Correct |
678 ms |
174572 KB |
Output is correct |
122 |
Correct |
612 ms |
173932 KB |
Output is correct |
123 |
Correct |
624 ms |
173932 KB |
Output is correct |
124 |
Correct |
670 ms |
174444 KB |
Output is correct |
125 |
Correct |
626 ms |
174128 KB |
Output is correct |
126 |
Correct |
652 ms |
173932 KB |
Output is correct |