結果

問題 No.2704 L to R Graph
ユーザー Magentor
提出日時 2024-03-11 22:13:34
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,995 ms / 3,000 ms
コード長 5,264 bytes
コンパイル時間 9,658 ms
コンパイル使用メモリ 357,368 KB
実行使用メモリ 107,264 KB
最終ジャッジ日時 2024-09-29 22:07:37
合計ジャッジ時間 45,528 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0