結果

問題 No.2704 L to R Graph
ユーザー MagentorMagentor
提出日時 2024-03-11 22:13:34
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,975 ms / 3,000 ms
コード長 5,264 bytes
コンパイル時間 9,247 ms
コンパイル使用メモリ 357,976 KB
実行使用メモリ 107,372 KB
最終ジャッジ日時 2024-03-11 22:14:22
合計ジャッジ時間 45,093 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 2 ms
6,676 KB
testcase_03 AC 3 ms
6,676 KB
testcase_04 AC 2 ms
6,676 KB
testcase_05 AC 2 ms
6,676 KB
testcase_06 AC 2 ms
6,676 KB
testcase_07 AC 3 ms
6,676 KB
testcase_08 AC 531 ms
71,696 KB
testcase_09 AC 512 ms
74,292 KB
testcase_10 AC 542 ms
71,372 KB
testcase_11 AC 1,917 ms
84,308 KB
testcase_12 AC 1,965 ms
86,356 KB
testcase_13 AC 1,897 ms
84,436 KB
testcase_14 AC 1,953 ms
86,612 KB
testcase_15 AC 1,904 ms
87,124 KB
testcase_16 AC 1,920 ms
86,484 KB
testcase_17 AC 1,951 ms
86,996 KB
testcase_18 AC 1,930 ms
86,612 KB
testcase_19 AC 1,945 ms
84,436 KB
testcase_20 AC 1,930 ms
87,124 KB
testcase_21 AC 1,935 ms
83,668 KB
testcase_22 AC 1,929 ms
81,876 KB
testcase_23 AC 1,915 ms
83,156 KB
testcase_24 AC 1,938 ms
83,156 KB
testcase_25 AC 1,975 ms
84,820 KB
testcase_26 AC 1,952 ms
84,564 KB
testcase_27 AC 389 ms
107,372 KB
testcase_28 AC 406 ms
107,372 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define rep2(i, m ,n) for (int i = (m); i < (long long)(n); i++)
#define REP(i, n) for (long long i = 1; i < (long long)(n); i++)
typedef long long ll;

ll floor(ll x, ll m) {
    return (x - ((x % m + m) % m)) / m;
}
struct graph{
  // 座圧を行う
  int n=0;
  ll sz;
  vector<ll> a;
  vector<ll> b;
  map<ll,ll> mp;
  vector<vector<ll>> table;
  vector<vector<ll>> child;
  set<ll> st;
  vector<ll> cycle;
  vector<ll> depth;
  vector<ll> ans1;
  vector<vector<ll>> ins;
  vector<vector<ll>> del;
  vector<ll> ans2;
  vector<ll> ans3;
  void add(int i,int j){
    mp[i] = a.size();
    n++;
    a.push_back(i);
    b.push_back(j);
  }
  void construction(int l,int r){
    if(n==0){return;}
  rep(i,n){mp[a[i]] = i;}
  table.resize(20);
  rep(i,20){table[i].resize(n);}
  rep(i,n){a[i] = mp[a[i]];b[i] = mp[b[i]];}
  table[0] = b;
  rep(i,19){
  rep(j,n){
  table[i+1][j] = table[i][table[i][j]];
    }
  }
  child.resize(n);
  rep(i,n){child[b[i]].push_back(i);}
  rep(i,n){st.insert(table[19][i]);}
  ll start = *st.begin();
  
  while(cycle.size()==0||cycle[0]!=b[cycle[cycle.size()-1]]){
    if(cycle.size()==0){cycle.push_back(start);continue;}
    cycle.push_back(b[cycle[cycle.size()-1]]);
  }
  sz = cycle.size();
  depth.resize(n);rep(i,n){depth[i] = 999999999LL;}
  queue<ll> q;
 rep(i,sz){q.push(cycle[i]);depth[cycle[i]] = 0;}
  while(!q.empty()){
    auto u = q.front();
    q.pop();
    rep(i,child[u].size()){
      if(depth[child[u][i]]==999999999LL){
        q.push(child[u][i]);
        depth[child[u][i]] = min(depth[child[u][i]],depth[u]+1);
      }
    }
  }
  ans1.resize(n);
  ans1[0] = 0;
  multiset<ll> mst;
  REP(i,n){
  if(0<=i-l&&ans1[i-l]!=-1){mst.insert(ans1[i-l]);}
  if(0<=i-r-1&&ans1[i-r-1]!=-1){mst.erase(mst.find(ans1[i-r-1]));}
  if(mst.size()==0){ans1[i] = -1;}
  else{ans1[i] = (*begin(mst))+1;}
  //cout << ans1[i]<<" ";
  }//cout<<endl;
  // 後で上にあげる！
  ins.resize(2*sz+1);
  del.resize(2*sz+1);
  ans2.resize(2*sz);
  multiset<ll> mst1;
  rep(i,cycle.size()+1){
  ins[min((2LL*sz),(i*l)%(ll)(sz))].push_back(i);
  del[min((2LL*sz),i*r+1-(ll)((i*l)/sz*sz))].push_back(i);
  }
  rep(i,2*sz){
    rep(j,ins[i].size()){mst1.insert(ins[i][j]);}
    rep(j,del[i].size()){mst1.erase(mst1.find(del[i][j]));}
    if(0==mst1.size()){ans2[i] = 999999999999LL;}
    else{
      ans2[i] = (*begin(mst1));
    }
  }
  ans3.resize(n+sz+1);
  set<ll> mst2;unordered_map<ll,ll> mst3;
  rep(i,sz){
    if(i==sz-1){ans3[i]=0;}
    else{ans3[i] = min(ans2[i+1],ans2[i+sz+1]);}}
    reverse(ans2.begin(),ans2.end());
  rep(i,sz){
    
    mst3[ans3[sz-i-1]] +=  floor((r-i),(ll)(sz))-floor((l-1-i),(ll)(sz));
    if(0<mst3[ans3[sz-i-1]]){mst2.insert(ans3[sz-i-1]);}
  }
  // for(auto u : mst3){cout<<"("<<u.first<<":"<<u.second<<")"<<" ";}cout<<endl;
    for(int i = sz;i<n+sz+1;i++){
      ll newl = i-l;
      if(0>newl){newl = (newl+200000000LL*sz)%sz;}
      mst3[ans3[newl]]++;
      
      if(mst3[ans3[newl]]==1){mst2.insert(ans3[newl]);}
      ll newr = i-r-1;
      //cout << newl << " "<<newr<<endl;
      if(0>newr){newr = (newr+200000000LL*sz)%sz;}
      mst3[ans3[newr]]--;
      if(mst3[ans3[newr]]==0){mst2.erase(ans3[newr]);}
      
     // cout << newl << " "<<newr<<endl;
     // for(auto u : mst3){cout<<"("<<u.first<<":"<<u.second<<")"<<" ";}cout<<endl;
      
      if(mst2.size()==0){assert(false);}

      ans3[i] = (*begin(mst2))+1;
    }
   // cout << cycle.size() << endl;
  // rep(i,ans2.size()){cout<<ans2[i]<<" ";}cout<<endl;
  // rep(i,ans3.size()){cout<<ans3[i]<<" ";}cout<<endl;
  }
  ll query(ll oldu,ll oldv){
    if(oldu==oldv){return 0;}
    ll u = mp[oldu];
    ll v = mp[oldv];
    ll dist = 0;
    if(st.count(v)){
      dist = depth[u];
      int now = u;
      rep(i,19){
        if((1LL << i) & (dist)){
          now = table[i][now];
        }
      }
      ll cycledist = (int)(find(cycle.begin(),cycle.end(),v)-find(cycle.begin(),cycle.end(),now));
      if(0>cycledist){cycledist += sz;}
      dist += cycledist;
      // cycleの場合の答え
      if(99999999<ans3[dist+sz-1]){return -1;}
      return ans3[dist+sz-1];
     
    }
    else{
      if(depth[u]<depth[v]){return -1;}
     // cout << depth[u]<<" "<<depth[v]<<endl;;
      ll now = u;
      rep(i,19){
        if((1LL << i) & (depth[u]-depth[v])){
          now = table[i][now];
        }
      }
      if(now==v){return ans1[depth[u]-depth[v]];}
      else{return -1;}
    }
  }
};
int main() {
int n,l,r;cin>>n>>l>>r;
vector<int> a(n);rep(i,n){cin>>a[i];a[i]--;}
dsu d(n);
rep(i,n){d.merge(a[i],i);}
vector<graph> v(n);
rep(i,n){
  v[d.leader(i)].add(i,a[i]);
}
rep(i,n){v[i].construction(l,r);}
int q;cin>>q;
rep(i,q){
  ll from,to;cin>>from>>to;from--;to--;
  if(!d.same(from,to)){cout<<-1<<endl;continue;}
  cout<<v[d.leader(from)].query(from,to)<<endl;
}
}
0