結果

問題 No.2704 L to R Graph
ユーザー lgswdnlgswdn
提出日時 2024-10-04 23:17:11
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 2,953 bytes
コンパイル時間 2,195 ms
コンパイル使用メモリ 216,044 KB
実行使用メモリ 28,016 KB
最終ジャッジ日時 2024-10-04 23:17:19
合計ジャッジ時間 6,495 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19 RE * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

//Shirasu Azusa 2024.09
#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}

#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
int read() {
	int x=0,w=1; char c=getchar(); 
	while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
	while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();} 
	return x*w;    
}

const int N=1e5+5;
int n,L,R,f[N],Q,id[N],sc[N],cnt,deg[N],vst[N],tr[N],d[N],dfn[N],sz[N],tick,ss[N],q[N],ans[N],dep[N],wsd[N];
vi gg[N],qr[N],te[N],e[N];

int find(int i) {return id[i]==i?i:id[i]=find(id[i]);}
void dfs(int u,int st) {
	dfn[u]=++tick, sz[u]=1, ss[u]=st;
	for(int v:e[u]) if(tr[v]) dep[v]=dep[u]+1, dfs(v,st), sz[u]+=sz[v];
}

signed main() {
	n=read(), L=read(), R=read();
	rep(i,1,n) f[i]=read(), deg[f[i]]++;
	rep(i,1,n) id[i]=i, e[f[i]].eb(i);
	rep(i,1,n) id[find(i)]=find(f[i]);
	rep(i,1,n) if(find(i)==i) sc[i]=++cnt;
	rep(i,1,n) sc[i]=sc[find(i)], gg[sc[i]].eb(i);
	queue<int> qq;
	rep(i,1,n) if(!deg[i]) qq.push(i);
	while(!qq.empty()) {
		int u=qq.front(); qq.pop(); tr[u]=1;
		--deg[f[u]]; if(!deg[f[u]]) qq.push(f[u]);
	}
	rep(i,1,cnt) {
		int x=0,tmp=0; for(int y:gg[i]) if(!tr[y]) x=y;
		for(;!vst[x];) {
			vst[x]=1; dfs(x,tmp++); x=f[x]; wsd[i]++;
		}
	}
	Q=read();
	rep(i,1,Q) {
		int s=read(), t=read(); int x=sc[find(s)];
		if(s==t) ans[i]=0;
		else if(find(s)!=find(t)) ans[i]=-1;
		else {
			if(tr[t]==1) {
				if(dfn[t]<=dfn[s]&&dfn[s]<dfn[t]+sz[t]) {
					int dis=dep[s]-dep[t];
					int mk=(dis+R-1)/R;
					if(mk*L>dis) ans[i]=-1;
					else ans[i]=mk;
				} else ans[i]=-1;
			} else {
				int d1=dep[s];
				int d2=ss[t]-ss[s];
				if(d2<0) d2+=wsd[x];
				q[i]=d1+d2, qr[x].eb(i);
			}
		}
	}
	rep(ts,1,cnt) {
		int w=wsd[ts], m=gg[ts].size();
		static int g[N];
		rep(i,0,m) g[i]=2*N;
		rep(i,0,m+1) te[i].clear();
		rep(k,1,m) {
			int l=L*k, r=R*k;
			if(l>m) {
				int g=ceil(l-m,w);
				l-=g*w, r-=g*w;
			}
			if(r-l>=m) {te[0].eb(k); break;}
			else if(r<=m) {
				te[l].eb(k), te[r+1].eb(-k);
			} else {
				te[l].eb(k); int x=r-m;
				te[m-w+1].eb(k), te[r-w+1].eb(-k);
			}
		}
		multiset<int> mst;
		rep(i,0,m) {
			for(int x:te[i]) {
				if(x>0) mst.insert(x);
				else mst.erase(mst.find(-x));
			}
			if(!mst.empty()) g[i]=*mst.begin();
		}
		per(i,m-w,0) chmin(g[i],g[i+w]);
		for(int i:qr[ts]) ans[i]=g[q[i]];
	}
	rep(i,1,Q) if(ans[i]>n) ans[i]=-1;
	rep(i,1,Q) printf("%d\n",ans[i]);
	return 0;
}
0