oj.uz

Submission #88971

# Submission time Handle Problem Language Result Execution time Memory
88971 2018-12-10T07:23:17 Z Lkvatashidze Special graph (IZhO13_specialg) C++17
0 / 100
 1000 ms 1548 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;

    int n, m;
    int g[100005];
    int BFS(int,int);

 int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

     cin >> n;
     for (int k=1; k<=n; k++) {
         int x;
          cin >> x;
          g[k]=x;
     }

    cin >> m;
     while (m--) {
        int type;
        cin >> type;
        if (type==1) {
           int x;
            cin >> x;
           g[x]=-1;
        }
        else{
            int a, b;
        cin >> a >> b;

            int ans=BFS(a,b);
        cout << ans << '\n';
        }
    }


    return 0;
}
   int BFS (int s, int fin) {

     vector < bool > used(n+1,0);
     vector < int > d(n+1,0);
     queue < int > Q;

     Q.push(s);
     used[s]=true;

      while (!Q.empty()) {
         int v=Q.front();
         Q.pop();
         if (g[v]==-1) continue;
         if (used[g[v]]) continue;
         d[g[v]]=d[v]+1;
         Q.push(g[v]);
         used[g[v]]=true;
      }
       if (used[fin]==0)
        return -1;

       return d[fin];
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 7 ms 500 KB Output is correct
3 Correct 8 ms 500 KB Output is correct
4 Correct 14 ms 500 KB Output is correct
5 Correct 8 ms 632 KB Output is correct
6 Correct 84 ms 660 KB Output is correct
7 Correct 93 ms 660 KB Output is correct
8 Correct 98 ms 848 KB Output is correct
9 Correct 82 ms 848 KB Output is correct
10 Correct 107 ms 928 KB Output is correct
11 Execution timed out 1035 ms 1548 KB Time limit exceeded
12 Halted 0 ms 0 KB -