#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define MAXN 100100
#define INF 1e17
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int M = 998244353;
const int X = 800;
vector<int> v[MAXN], w[MAXN];
vector<pii> atual, sq[MAXN];
int vis[MAXN], dp[MAXN];
void merg(int node) {
atual = sq[node];
vector<pii> novo;
for (int i = 0; i < (int)atual.size(); i++) {
if (i == (int)atual.size() -1 || atual[i].F != atual[i+1].F) novo.pb(atual[i]);
}
atual = novo;
sort(atual.begin(), atual.end(), [&] (pii x, pii y) { return x.S > y.S; });
while ((int)atual.size() > X) atual.pop_back();
sq[node] = atual;
for (pii &x : atual) x.S++;
sort(atual.begin(), atual.end());
for (int x : w[node]) {
novo = sq[x];
sq[x].resize((int)sq[x].size() + (int)atual.size());
merge(novo.begin(), novo.end(), atual.begin(), atual.end(), sq[x].begin());
}
}
void dfs(int node) {
vis[node] = 1;
for (int x : v[node]) {
if (!vis[x]) dfs(x);
dp[node] = max(dp[node], 1 + dp[x]);
}
}
int main() { _
int n, m, q, a, b;
cin >> n >> m >> q;
for (int i = 0; i < m; i++) {
cin >> a >> b;
v[b].pb(a);
w[a].pb(b);
}
for (int i = 1; i <= n; i++) sq[i].pb({i, 0});
for (int i = 1; i <= n; i++) {
merg(i);
}
int d, tot, aux;
for (int i = 0; i < q; i++) {
cin >> d >> tot;
set<int> inv;
for (int j = 0; j < tot; j++) {
cin >> aux;
inv.insert(aux);
}
if (tot < X) {
int ans = -1;
for (pii x : sq[d]) {
if (!inv.count(x.F)) ans = max(ans, x.S);
}
cout << ans << '\n';
}
if (tot >= X) {
memset(dp, 0, sizeof(dp));
memset(vis, 0, sizeof(vis));
dfs(d);
int ans = -1;
for (int i = 1; i <= n; i++) {
if (!inv.count(i)) ans = max(ans, dp[i]);
}
cout << ans << '\n';
}
}
return 0;
}
/* stuff you should look for
* int overflow, array bounds
* special cases (lowest n, greatest n)
* RTE MAXN
* WRITE/DRAW STUFF DOWN
* DONT OVERCOMPLICATE
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7372 KB |
Output is correct |
2 |
Correct |
6 ms |
7372 KB |
Output is correct |
3 |
Correct |
5 ms |
7380 KB |
Output is correct |
4 |
Correct |
5 ms |
7360 KB |
Output is correct |
5 |
Correct |
9 ms |
8012 KB |
Output is correct |
6 |
Correct |
9 ms |
8012 KB |
Output is correct |
7 |
Correct |
9 ms |
8036 KB |
Output is correct |
8 |
Correct |
34 ms |
14668 KB |
Output is correct |
9 |
Correct |
30 ms |
14532 KB |
Output is correct |
10 |
Correct |
30 ms |
14532 KB |
Output is correct |
11 |
Correct |
37 ms |
11820 KB |
Output is correct |
12 |
Correct |
16 ms |
8780 KB |
Output is correct |
13 |
Correct |
36 ms |
11616 KB |
Output is correct |
14 |
Correct |
31 ms |
13488 KB |
Output is correct |
15 |
Correct |
23 ms |
10072 KB |
Output is correct |
16 |
Correct |
29 ms |
13112 KB |
Output is correct |
17 |
Correct |
28 ms |
11648 KB |
Output is correct |
18 |
Correct |
20 ms |
9164 KB |
Output is correct |
19 |
Correct |
28 ms |
11596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7372 KB |
Output is correct |
2 |
Correct |
6 ms |
7372 KB |
Output is correct |
3 |
Correct |
5 ms |
7380 KB |
Output is correct |
4 |
Correct |
5 ms |
7360 KB |
Output is correct |
5 |
Correct |
9 ms |
8012 KB |
Output is correct |
6 |
Correct |
9 ms |
8012 KB |
Output is correct |
7 |
Correct |
9 ms |
8036 KB |
Output is correct |
8 |
Correct |
34 ms |
14668 KB |
Output is correct |
9 |
Correct |
30 ms |
14532 KB |
Output is correct |
10 |
Correct |
30 ms |
14532 KB |
Output is correct |
11 |
Correct |
37 ms |
11820 KB |
Output is correct |
12 |
Correct |
16 ms |
8780 KB |
Output is correct |
13 |
Correct |
36 ms |
11616 KB |
Output is correct |
14 |
Correct |
31 ms |
13488 KB |
Output is correct |
15 |
Correct |
23 ms |
10072 KB |
Output is correct |
16 |
Correct |
29 ms |
13112 KB |
Output is correct |
17 |
Correct |
28 ms |
11648 KB |
Output is correct |
18 |
Correct |
20 ms |
9164 KB |
Output is correct |
19 |
Correct |
28 ms |
11596 KB |
Output is correct |
20 |
Execution timed out |
2075 ms |
159796 KB |
Time limit exceeded |
21 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7372 KB |
Output is correct |
2 |
Correct |
6 ms |
7372 KB |
Output is correct |
3 |
Correct |
5 ms |
7380 KB |
Output is correct |
4 |
Correct |
5 ms |
7360 KB |
Output is correct |
5 |
Correct |
9 ms |
8012 KB |
Output is correct |
6 |
Correct |
9 ms |
8012 KB |
Output is correct |
7 |
Correct |
9 ms |
8036 KB |
Output is correct |
8 |
Correct |
34 ms |
14668 KB |
Output is correct |
9 |
Correct |
30 ms |
14532 KB |
Output is correct |
10 |
Correct |
30 ms |
14532 KB |
Output is correct |
11 |
Correct |
37 ms |
11820 KB |
Output is correct |
12 |
Correct |
16 ms |
8780 KB |
Output is correct |
13 |
Correct |
36 ms |
11616 KB |
Output is correct |
14 |
Correct |
31 ms |
13488 KB |
Output is correct |
15 |
Correct |
23 ms |
10072 KB |
Output is correct |
16 |
Correct |
29 ms |
13112 KB |
Output is correct |
17 |
Correct |
28 ms |
11648 KB |
Output is correct |
18 |
Correct |
20 ms |
9164 KB |
Output is correct |
19 |
Correct |
28 ms |
11596 KB |
Output is correct |
20 |
Execution timed out |
2075 ms |
159796 KB |
Time limit exceeded |
21 |
Halted |
0 ms |
0 KB |
- |