結果
問題 | No.2704 L to R Graph |
ユーザー |
![]() |
提出日時 | 2024-03-11 22:11:08 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,273 bytes |
コンパイル時間 | 8,429 ms |
コンパイル使用メモリ | 359,236 KB |
実行使用メモリ | 106,512 KB |
最終ジャッジ日時 | 2024-09-29 22:06:51 |
合計ジャッジ時間 | 40,330 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | AC * 24 RE * 2 |
ソースコード
#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 sz;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(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;}}