Submission #1159536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159536		lopkus	Passport (JOI23_passport)	C++20	0 / 100	768 ms	1114112 KiB

passport

#include <bits/stdc++.h>

#define int long long

using namespace std;

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<pair<int,int>> a(n + 1);
  vector<int> adj[n + 1];
  for(int i = 1; i <= n; i++) {
    int l, r;
    cin >> l >> r;
    for(int j = l; j <= r; j++) {
      adj[i].push_back(j);
    }
  }
  vector<vector<int>> dist(n + 1, vector<int>(n + 1));
  for(int i = 0; i <= n; i++) {
    for(int j = 0; j <= n; j++) {
      dist[i][j] = n + 1;
    }
  }
  vector<int> ans(n + 1);
  function<void(int)> bfs = [&](int x) {
    dist[x][x] = 0;
    queue<int> Q;
    Q.push(x);
    while(!Q.empty()) {
      int u = Q.front();
      Q.pop();
      for(auto v : adj[u]) {
        if(dist[x][v] == n + 1) {
          dist[x][v] = dist[x][u] + 1;
          Q.push(v);
        }
      }
    }
  };
  for(int i = 1; i <= n; i++) {
    bfs(i);
    for(int j = 1; j <= n; j++) {
      ans[i] = max(ans[i], dist[i][j]);
    }
  }
  int q;
  cin >> q;
  while(q--) {
    int x;
    cin >> x;
    cout << (ans[x] == n + 1 ? - 1 : ans[x]) << "\n";
  }
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46