oj.uz

Submission #47748

# Submission time Handle Problem Language Result Execution time Memory
47748 2018-05-07T04:28:17 Z mirbek01 Bitaro’s Party (JOI18_bitaro) C++17
0 / 100
 6 ms 3744 KB 
# include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

int n, m, q, d[N], used[N], vis[N];
vector <int> g[N];

int main(){
      cin >> n >> m >> q;

      for(int i = 0; i < m; i ++){
            int u, v;
            cin >> u >> v;
            g[v].push_back(u);
      }

      while(q --){
            int t, y;
            cin >> t >> y;
            vector <int> v;
            for(int i = 1; i <= y; i ++){
                  int x;
                  cin >> x;
                  used[x] = 1;
                  v.push_back(x);
            }

            queue <int> q;
            q.push(t);
            memset(d, 0, sizeof(d));
            memset(vis, 0, sizeof(vis));
            vis[t] = 1;

            int ans = -1;

            while(!q.empty()){
                  int v = q.front();
                  q.pop();
                  for(int to : g[v]){
                        if(!vis[to])
                              q.push(to);
                        vis[to] = 1;
                        d[to] = max(d[v] + 1, d[to]);
                  }
            }

            for(int i = 1; i <= n; i ++){
                  if(!used[i] && vis[i]) ans = max(ans, d[i]);
            }

            cout << ans << endl;

            for(int i : v)
                  used[i] = 0;
      }
}
/**
5 6 1
1 2
2 4
3 4
1 3
3 5
4 5
5 2 2 3
**/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3448 KB Output is correct
2 Correct 6 ms 3448 KB Output is correct
3 Correct 5 ms 3520 KB Output is correct
4 Correct 6 ms 3540 KB Output is correct
5 Incorrect 6 ms 3744 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3448 KB Output is correct
2 Correct 6 ms 3448 KB Output is correct
3 Correct 5 ms 3520 KB Output is correct
4 Correct 6 ms 3540 KB Output is correct
5 Incorrect 6 ms 3744 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3448 KB Output is correct
2 Correct 6 ms 3448 KB Output is correct
3 Correct 5 ms 3520 KB Output is correct
4 Correct 6 ms 3540 KB Output is correct
5 Incorrect 6 ms 3744 KB Output isn't correct
6 Halted 0 ms 0 KB -