oj.uz

Submission #88966

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

    int n, m;
    map < int, int > mp;
    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;
           mp[x]=true;
        }
        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 (mp[v]) 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 9 ms 504 KB Output is correct
2 Correct 12 ms 560 KB Output is correct
3 Correct 11 ms 748 KB Output is correct
4 Correct 16 ms 748 KB Output is correct
5 Correct 11 ms 852 KB Output is correct
6 Correct 510 ms 1176 KB Output is correct
7 Correct 572 ms 1676 KB Output is correct
8 Correct 649 ms 1940 KB Output is correct
9 Correct 539 ms 2136 KB Output is correct
10 Correct 707 ms 2360 KB Output is correct
11 Execution timed out 1072 ms 8204 KB Time limit exceeded
12 Halted 0 ms 0 KB -