結果

問題 No.2704 L to R Graph
ユーザー MagentorMagentor
提出日時 2024-03-11 05:32:32
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,255 ms / 3,000 ms
コード長 5,439 bytes
コンパイル時間 6,747 ms
コンパイル使用メモリ 337,520 KB
実行使用メモリ 115,108 KB
最終ジャッジ日時 2024-09-29 21:55:36
合計ジャッジ時間 44,060 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 3 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 3 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 505 ms
74,500 KB
testcase_09 AC 500 ms
77,152 KB
testcase_10 AC 500 ms
74,308 KB
testcase_11 AC 1,926 ms
87,188 KB
testcase_12 AC 1,943 ms
89,420 KB
testcase_13 AC 1,910 ms
87,500 KB
testcase_14 AC 2,073 ms
89,676 KB
testcase_15 AC 2,096 ms
90,060 KB
testcase_16 AC 1,962 ms
89,548 KB
testcase_17 AC 1,890 ms
89,928 KB
testcase_18 AC 2,068 ms
89,548 KB
testcase_19 AC 2,187 ms
87,376 KB
testcase_20 AC 2,204 ms
90,192 KB
testcase_21 AC 2,255 ms
86,860 KB
testcase_22 AC 2,179 ms
84,940 KB
testcase_23 AC 2,204 ms
86,576 KB
testcase_24 AC 1,895 ms
86,600 KB
testcase_25 AC 2,238 ms
88,488 KB
testcase_26 AC 2,250 ms
87,616 KB
testcase_27 AC 386 ms
115,072 KB
testcase_28 AC 384 ms
115,108 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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) {
    ll r = (x % m + m) % m;
    return (x - r) / m;
}
struct graph{
  // 座圧を行う
  int n=0;
  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(25);
  rep(i,25){table[i].resize(n);}
  rep(i,n){a[i] = mp[a[i]];b[i] = mp[b[i]];}
  table[0] = b;
  rep(i,24){
  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[24][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]]);
  }
  depth.resize(n);rep(i,n){depth[i] = 999999999LL;}
  queue<ll> q;
 rep(i,cycle.size()){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*cycle.size()+1);
  del.resize(2*cycle.size()+1);
  ans2.resize(2*cycle.size());
  multiset<ll> mst1;
  rep(i,cycle.size()+1){
  ins[min((ll)(2LL*cycle.size()),(i*l)%(ll)(cycle.size()))].push_back(i);
  del[min((ll)(2LL*cycle.size()),i*r+1-(ll)((i*l)/cycle.size()*cycle.size()))].push_back(i);
  }
  rep(i,2*cycle.size()){
    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+cycle.size()+1);
  set<ll> mst2;map<ll,ll> mst3;
  rep(i,cycle.size()){
    if(i==cycle.size()-1){ans3[i]=0;}
    else{ans3[i] = min(ans2[i+1],ans2[i+cycle.size()+1]);}}
    reverse(ans2.begin(),ans2.end());
  rep(i,cycle.size()){
    
    mst3[ans3[cycle.size()-i-1]] +=  floor((r-i),(ll)(cycle.size()))-floor((l-1-i),(ll)(cycle.size()));
    if(0<mst3[ans3[cycle.size()-i-1]]){mst2.insert(ans3[cycle.size()-i-1]);}
  }
  // for(auto u : mst3){cout<<"("<<u.first<<":"<<u.second<<")"<<" ";}cout<<endl;
    for(int i = cycle.size();i<n+cycle.size()+1;i++){
      ll newl = i-l;
      if(0>newl){newl = (newl+200000000LL*cycle.size())%cycle.size();}
      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*cycle.size())%cycle.size();}
      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,24){
        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 += cycle.size();}
      dist += cycledist;
      // cycleの場合の答え
      if(99999999<ans3[dist+cycle.size()-1]){return -1;}
      return ans3[dist+cycle.size()-1];
     
    }
    else{
      if(depth[u]<depth[v]){return -1;}
     // cout << depth[u]<<" "<<depth[v]<<endl;;
      ll now = u;
      rep(i,24){
        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