Submission #834621

#	Time	Username	Problem	Language	Result	Execution time	Memory
834621		kwongweng	Passport (JOI23_passport)	C++17	100 / 100	808 ms	16056 KiB

passport

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second

/* Consider directed graph formed by constructing edge i -> j for all j in [l[i], r[i]]
problem becomes finding for each 1<=i<=n :
min # vertices to pass through to reach vertex 1 and vertex n
there are 2 cases:
1) 2 disjoint paths, one from i to 1, one from i to n
2) another vertex j, 3 disjoint paths, (i to j, j to 1, j to n)

So we can find use bfs to find min dist from each i to 1 and to n
Then a third bfs to deal with the cases. (smth similar to dijkstra)
* note : directions are reversed here

Issue : There are O(n^2) edges, so total runtime is O(n^2) with naive bfs
Solution : we need smarter bfs which ignores useless edge
How can bfs be smarter?
Let u be current vertex, we need to efficiently find v so that u->v and v not visited
Obs : u-> v if
1) v < u and r[v] >= u
2) u < v and l[v] <= u
Hence we can efficiently maintain 2 segment trees to find v in O(log n)
1) find v so that r[v]=max(1<=w<=u, w not visited).
2) find v so that l[v]=min(u<=w<=n, w not visited).

Finally, the third bfs can employ the same idea to finish.
*/

struct segtree{
  int sz; vi mx; vi a;
  void build(int v, int tl, int tr){
    if (tl==tr) {mx[v]=tl; return;}
    int tm=(tl+tr)/2;
    build(2*v,tl,tm); build(2*v+1,tm+1,tr);
    if (a[mx[2*v]] >= a[mx[2*v+1]]) mx[v]=mx[2*v];
    else mx[v]=mx[2*v+1];
  }
  void init(int n, vi A){
    sz=n; mx.assign(4*n,-1); a=A; build(1,0,n-1);
  }
  void rem(int v, int tl, int tr, int pos){
    if (tl==tr){mx[v]=-1; return;}
    int tm=(tl+tr)/2;
    if (pos<=tm) rem(2*v,tl,tm,pos);
    else rem(2*v+1,tm+1,tr,pos);
    if (mx[2*v] != -1 && mx[2*v+1] != -1){
      if (a[mx[2*v]] >= a[mx[2*v+1]]) mx[v]=mx[2*v];
      else mx[v]=mx[2*v+1];
    }else{
      if (mx[2*v]==-1) mx[v]=mx[2*v+1];
      else mx[v]=mx[2*v];
    }
  }
  void rem(int pos){rem(1,0,sz-1,pos);}
  int qry(int v, int tl, int tr, int l, int r){
    if (tl==l && tr==r) return mx[v];
    if (l>r) return -1;
    int tm=(tl+tr)/2;
    int L=qry(2*v,tl,tm,l,min(r,tm)), R=qry(2*v+1,tm+1,tr,max(l,tm+1),r);
    if (L==-1) return R;
    if (R==-1) return L;
    if (a[L]>=a[R]) return L;
    return R;
  }
  int qry(int l, int r){return qry(1,0,sz-1,l,r);}
};

void solve(){
  int n; cin>>n;
  vi l(n+1), r(n+1);
  FOR(i,1,n+1) cin>>l[i]>>r[i];
  FOR(i,1,n+1) l[i]=n-l[i];
  segtree stl, str;
  stl.init(n+1,l); str.init(n+1,r);
  vi d1(n+1,n+2); queue<int> bfs; 
  d1[1]=0; stl.rem(1); str.rem(1); bfs.push(1);
  while (!bfs.empty()){
    int u = bfs.front(); bfs.pop();
    int val = str.qry(1,u);
    while (val != -1 && r[val] >= u){
      stl.rem(val); str.rem(val); bfs.push(val); d1[val]=d1[u]+1;
      //cout<<u<<" "<<d1[u]<<" "<<val<<" "<<d1[val]<<"\n";
      val=str.qry(1,u);
    }
    val = stl.qry(u,n);
    while (val!=-1 && l[val] >= n-u){
      stl.rem(val); str.rem(val); bfs.push(val); d1[val]=d1[u]+1;
      //cout<<u<<" "<<d1[u]<<" "<<val<<" "<<d1[val]<<"\n";
      val=stl.qry(u,n);
    }
  }
  //FOR(i,1,n+1) cout<<d1[i]<<" "; cout<<"\n";

  vi dn(n+1,n+2);
  stl.init(n+1,l); str.init(n+1,r);
  dn[n]=0; stl.rem(n); str.rem(n); bfs.push(n);
  while (!bfs.empty()){
    int u = bfs.front(); bfs.pop();
    int val = str.qry(1,u);
    while (val != -1 && r[val] >= u){
      stl.rem(val); str.rem(val); bfs.push(val); dn[val]=dn[u]+1;
      val=str.qry(1,u);
    }
    val = stl.qry(u,n);
    while (val!=-1 && l[val] >= n-u){
      stl.rem(val); str.rem(val); bfs.push(val); dn[val]=dn[u]+1;
      val=stl.qry(u,n);
    }
  }
  //FOR(i,1,n+1) cout<<dn[i]<<" "; cout<<"\n";
  
  vi ans(n+1); FOR(i,1,n+1) ans[i]=d1[i]+dn[i]-1; ans[1]++; ans[n]++;
  int mn=ans[1]; FOR(i,2,n+1) mn=min(mn,ans[1]);
  stl.init(n+1,l); str.init(n+1,r);
  priority_queue<ii,vii,greater<ii>> pq;
  FOR(i,1,n+1){
    if (ans[i]<=n) pq.push({ans[i],i});
  }
  while (!pq.empty()){
    ii node = pq.top(); pq.pop();
    int u = node.se;
    if (ans[u] != node.fi) continue;
    int val = str.qry(1,u);
    while (val != -1 && r[val] >= u){
      stl.rem(val); str.rem(val); bfs.push(val);
      if (ans[val] > ans[u]+1){
        ans[val]=ans[u]+1; pq.push({ans[val],val});
      }
      val=str.qry(1,u);
    }
    val = stl.qry(u,n);
    while (val!=-1 && l[val] >= n-u){
      stl.rem(val); str.rem(val); bfs.push(val);
      if (ans[val] > ans[u]+1){
        ans[val]=ans[u]+1; pq.push({ans[val],val});
      }
      val=stl.qry(u,n);
    }
  }
  
  int q; cin>>q;
  while(q--){
    int x; cin>>x; 
    if (ans[x]>n) ans[x]=-1;
    cout<<ans[x]<<"\n";
  }
  
}

int main(){
	//MOD=MOD1;
    ios::sync_with_stdio(false);
    if (fopen("input.txt", "r")) {
		  freopen("input.txt", "r", stdin);
    	freopen("output.txt", "w", stdout);
	  }
    int TC = 1;
    //cin >> TC; 
    FOR(i, 1, TC+1){
        //cout << "Case #" << i << ": ";
        solve();
    }
	
	return 0;
}

Compilation message (stderr)

passport.cpp: In function 'int main()':
passport.cpp:166:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:167:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |      freopen("output.txt", "w", stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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