#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
const int b = 1;
set<pair<int,int> > st[maxn];
vector<int>ig[maxn], g[maxn];
vector<int>order;
int n, m, q;
bool blocked[maxn];
bool visited[maxn];
int dp[maxn];
void dfs(int node) {
if(visited[node]) return;
visited[node] = true;
for(int i:ig[node]) {
if(!visited[i]) {
dfs(i);
}
}
order.pb(node);
}
int brute_force(int node) {
dfs(node);
reverse(order.begin(), order.end());
int result = -1;
for(int i=0;i<order.size();i++) {
int node=order[i];
for(int i:g[node]) {
if(!visited[i]) continue;
dp[node] = max(dp[node], dp[i] + 1);
}
//cout<<node<<": "<<dp[node]<<"\n";
if(!blocked[node])
result = max(result, dp[node]);
}
memset(dp, 0, sizeof(dp));
memset(visited,false,sizeof(visited));
order.clear();
return result;
}
void preprocess() {
for(int node=1;node<=n;node++) {
st[node].insert(mp(0, node));
map<int, int> dists;
for(int i:ig[node]) {
//update st[node] with values from st[i] + 1
// Possible optimization point, in case of TLE
for(auto vals:st[i]) {
dists[vals.second] = max(dists[vals.second], vals.first + 1);
}
}
for(auto i:dists) {
st[node].insert(mp(i.second, i.first));
if(st[node].size() > b) st[node].erase(st[node].begin());
}
}
}
void solve() {
int node, qs, x;
vector<int>points;
cin>>node>>qs;
for(int i=0;i<qs;i++) {
cin>>x;
points.pb(x);
blocked[x] = true;
}
//if(qs >= b) {
cout<<brute_force(node);
for(int i:points) blocked[i] = false;
return;
//}
/*int maxtunnels = -1;
for(auto i:st[node]) {
if(!blocked[i.second]) maxtunnels = max(maxtunnels, i.first);
}
cout<<maxtunnels<<"\n";
for(int i:points) blocked[i] = false;*/
}
int main() {
cin>>n>>m>>q;
int a, b;
for(int i=0;i<m;i++) {
cin>>a>>b;
g[a].pb(b);
ig[b].pb(a);
}
//preprocess();
while(q--) {
solve();
}
}
Compilation message
bitaro.cpp: In function 'int brute_force(int)':
bitaro.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<order.size();i++) {
~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
10240 KB |
Output is correct |
2 |
Correct |
10 ms |
10240 KB |
Output is correct |
3 |
Correct |
10 ms |
10240 KB |
Output is correct |
4 |
Correct |
10 ms |
10240 KB |
Output is correct |
5 |
Correct |
11 ms |
10240 KB |
Output is correct |
6 |
Correct |
11 ms |
10240 KB |
Output is correct |
7 |
Correct |
12 ms |
10240 KB |
Output is correct |
8 |
Correct |
12 ms |
10368 KB |
Output is correct |
9 |
Correct |
12 ms |
10368 KB |
Output is correct |
10 |
Correct |
12 ms |
10240 KB |
Output is correct |
11 |
Correct |
11 ms |
10240 KB |
Output is correct |
12 |
Correct |
12 ms |
10240 KB |
Output is correct |
13 |
Correct |
12 ms |
10240 KB |
Output is correct |
14 |
Correct |
13 ms |
10240 KB |
Output is correct |
15 |
Correct |
12 ms |
10240 KB |
Output is correct |
16 |
Correct |
12 ms |
10240 KB |
Output is correct |
17 |
Correct |
12 ms |
10240 KB |
Output is correct |
18 |
Correct |
12 ms |
10240 KB |
Output is correct |
19 |
Correct |
11 ms |
10240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
10240 KB |
Output is correct |
2 |
Correct |
10 ms |
10240 KB |
Output is correct |
3 |
Correct |
10 ms |
10240 KB |
Output is correct |
4 |
Correct |
10 ms |
10240 KB |
Output is correct |
5 |
Correct |
11 ms |
10240 KB |
Output is correct |
6 |
Correct |
11 ms |
10240 KB |
Output is correct |
7 |
Correct |
12 ms |
10240 KB |
Output is correct |
8 |
Correct |
12 ms |
10368 KB |
Output is correct |
9 |
Correct |
12 ms |
10368 KB |
Output is correct |
10 |
Correct |
12 ms |
10240 KB |
Output is correct |
11 |
Correct |
11 ms |
10240 KB |
Output is correct |
12 |
Correct |
12 ms |
10240 KB |
Output is correct |
13 |
Correct |
12 ms |
10240 KB |
Output is correct |
14 |
Correct |
13 ms |
10240 KB |
Output is correct |
15 |
Correct |
12 ms |
10240 KB |
Output is correct |
16 |
Correct |
12 ms |
10240 KB |
Output is correct |
17 |
Correct |
12 ms |
10240 KB |
Output is correct |
18 |
Correct |
12 ms |
10240 KB |
Output is correct |
19 |
Correct |
11 ms |
10240 KB |
Output is correct |
20 |
Correct |
143 ms |
12536 KB |
Output is correct |
21 |
Correct |
138 ms |
14200 KB |
Output is correct |
22 |
Correct |
141 ms |
14200 KB |
Output is correct |
23 |
Correct |
141 ms |
14200 KB |
Output is correct |
24 |
Correct |
249 ms |
18292 KB |
Output is correct |
25 |
Correct |
260 ms |
18396 KB |
Output is correct |
26 |
Correct |
250 ms |
18292 KB |
Output is correct |
27 |
Correct |
256 ms |
22732 KB |
Output is correct |
28 |
Correct |
250 ms |
22952 KB |
Output is correct |
29 |
Correct |
259 ms |
23992 KB |
Output is correct |
30 |
Correct |
240 ms |
19192 KB |
Output is correct |
31 |
Correct |
243 ms |
19192 KB |
Output is correct |
32 |
Correct |
241 ms |
19316 KB |
Output is correct |
33 |
Correct |
248 ms |
19188 KB |
Output is correct |
34 |
Correct |
250 ms |
19192 KB |
Output is correct |
35 |
Correct |
243 ms |
19188 KB |
Output is correct |
36 |
Correct |
264 ms |
19392 KB |
Output is correct |
37 |
Correct |
243 ms |
19320 KB |
Output is correct |
38 |
Correct |
241 ms |
19316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
10240 KB |
Output is correct |
2 |
Correct |
10 ms |
10240 KB |
Output is correct |
3 |
Correct |
10 ms |
10240 KB |
Output is correct |
4 |
Correct |
10 ms |
10240 KB |
Output is correct |
5 |
Correct |
11 ms |
10240 KB |
Output is correct |
6 |
Correct |
11 ms |
10240 KB |
Output is correct |
7 |
Correct |
12 ms |
10240 KB |
Output is correct |
8 |
Correct |
12 ms |
10368 KB |
Output is correct |
9 |
Correct |
12 ms |
10368 KB |
Output is correct |
10 |
Correct |
12 ms |
10240 KB |
Output is correct |
11 |
Correct |
11 ms |
10240 KB |
Output is correct |
12 |
Correct |
12 ms |
10240 KB |
Output is correct |
13 |
Correct |
12 ms |
10240 KB |
Output is correct |
14 |
Correct |
13 ms |
10240 KB |
Output is correct |
15 |
Correct |
12 ms |
10240 KB |
Output is correct |
16 |
Correct |
12 ms |
10240 KB |
Output is correct |
17 |
Correct |
12 ms |
10240 KB |
Output is correct |
18 |
Correct |
12 ms |
10240 KB |
Output is correct |
19 |
Correct |
11 ms |
10240 KB |
Output is correct |
20 |
Correct |
143 ms |
12536 KB |
Output is correct |
21 |
Correct |
138 ms |
14200 KB |
Output is correct |
22 |
Correct |
141 ms |
14200 KB |
Output is correct |
23 |
Correct |
141 ms |
14200 KB |
Output is correct |
24 |
Correct |
249 ms |
18292 KB |
Output is correct |
25 |
Correct |
260 ms |
18396 KB |
Output is correct |
26 |
Correct |
250 ms |
18292 KB |
Output is correct |
27 |
Correct |
256 ms |
22732 KB |
Output is correct |
28 |
Correct |
250 ms |
22952 KB |
Output is correct |
29 |
Correct |
259 ms |
23992 KB |
Output is correct |
30 |
Correct |
240 ms |
19192 KB |
Output is correct |
31 |
Correct |
243 ms |
19192 KB |
Output is correct |
32 |
Correct |
241 ms |
19316 KB |
Output is correct |
33 |
Correct |
248 ms |
19188 KB |
Output is correct |
34 |
Correct |
250 ms |
19192 KB |
Output is correct |
35 |
Correct |
243 ms |
19188 KB |
Output is correct |
36 |
Correct |
264 ms |
19392 KB |
Output is correct |
37 |
Correct |
243 ms |
19320 KB |
Output is correct |
38 |
Correct |
241 ms |
19316 KB |
Output is correct |
39 |
Execution timed out |
2087 ms |
18496 KB |
Time limit exceeded |
40 |
Halted |
0 ms |
0 KB |
- |