Submission #1117770

#TimeUsernameProblemLanguageResultExecution timeMemory
1117770ntdaccodePassport (JOI23_passport)C++17
100 / 100
738 ms87580 KiB
#include<bits/stdc++.h> #define fori(i,a,b) for(int i=a;i<=b;i++) #define ll long long #define ii pair<int,int> #define fi first #define se second #define pb push_back using namespace std; const int mod=1e9+7; const int M=2e5+10; const int N=1e3+10; int n,q; // int pos[M]; vector<ii> ke[4*M]; void build(int s,int l,int r) { if(l==r) { pos[l]=s; return ; } int mid=(l+r)/2; build(s*2,l,mid); build(s*2+1,mid+1,r); ke[s*2].pb({s,0}); ke[s*2+1].pb({s,0}); } void upd(int s,int l,int r,int u,int v,int p) { if(l>v||r<u) return ; if(u<=l&&r<=v) { ke[s].pb({p,1}); return ; } int mid=(l+r)/2; upd(s*2,l,mid,u,v,p); upd(s*2+1,mid+1,r,u,v,p); } int d[4*M],f[4*M]; priority_queue<ii,vector<ii>,greater<ii> > h; void dij() { while(!h.empty()) { ii u=h.top();h.pop(); if(d[u.se]>u.fi) continue; for(ii v : ke[u.se]) { if(d[v.fi]>u.fi+v.se) { d[v.fi]=u.fi+v.se; h.push({d[v.fi],v.fi}); } } } } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define task "1" if(fopen(task".inp","r")) { freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } cin >> n; build(1,1,n); fori(i,1,n) { int l,r; cin >> l >> r; upd(1,1,n,l,r,pos[i]); } fori(i,1,4*n) d[i]=1e9; d[pos[1]]=0; h.push({0,pos[1]}); dij(); fori(i,1,4*n) f[i]=d[i]; fori(i,1,4*n) d[i]=1e9; d[pos[n]]=0; h.push({0,pos[n]}); dij(); fori(i,1,4*n) f[i]+=d[i]; fori(i,2,n-1) f[pos[i]]--; fori(i,1,4*n) { h.push({f[i],i}); d[i]=f[i]; } dij(); cin >> q; while(q--) { int p; cin >> p; if(d[pos[p]]<1e8)cout << d[pos[p]]<< "\n"; else cout << -1 << "\n"; } }

Compilation message (stderr)

passport.cpp: In function 'int32_t main()':
passport.cpp:67:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
passport.cpp:68:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...