Submission #997500

#TimeUsernameProblemLanguageResultExecution timeMemory
997500AbitoPassport (JOI23_passport)C++17
0 / 100
2100 ms530648 KiB
#include <bits/stdc++.h> #define F first #define S second #define pb push_back #define ppb pop_back #define ep insert #define endl '\n' #define elif else if #define pow pwr #define sqrt sqrtt #define int long long #define ll long long #define y1 YONE typedef unsigned long long ull; using namespace std; const int N=2e5+5; int dis[N],L[N],R[N],n,q; bool vis[N]; void dijkstra(int s){ for (int i=1;i<=n;i++) dis[i]=INT_MAX,vis[i]=0; dis[s]=0; priority_queue<pair<int,int>> pq; pq.push({0,s}); while (!pq.empty()){ int x=pq.top().S; pq.pop(); if (vis[x]) continue; vis[x]=1; for (int i=L[x];i<=R[x];i++){ if (dis[i]<dis[x]+1) continue; dis[i]=dis[x]+1; pq.push({-dis[i],i}); } }return; } int32_t main(){ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); cin>>n; for (int i=1;i<=n;i++) cin>>L[i]>>R[i]; cin>>q; while (q--){ int x;cin>>x; dijkstra(x); int mx=0; for (int i=1;i<=n;i++) mx=max(mx,dis[i]); if (mx>=INT_MAX) cout<<-1<<endl; else cout<<mx<<endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...