結果

問題 No.2704 L to R Graph
コンテスト
ユーザー kotatsugame
提出日時 2024-03-29 23:24:54
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,201 bytes
コンパイル時間 1,140 ms
コンパイル使用メモリ 85,672 KB
実行使用メモリ 18,536 KB
最終ジャッジ日時 2024-09-30 16:55:28
合計ジャッジ時間 7,195 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 WA * 3 TLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<queue>
#include<cassert>
#include<atcoder/dsu>
using namespace std;
int N,A[1<<17];
int indeg[1<<17];
int L,R,Q;
vector<int>G[1<<17];
int depth[1<<17],root[1<<17];
void dfs(int u,int r,int d)
{
	root[u]=r;
	depth[u]=d;
	for(int v:G[u])dfs(v,r,d+1);
}
int idx[1<<17],len[1<<17];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N>>L>>R;
	atcoder::dsu uf(N);
	for(int i=0;i<N;i++)
	{
		cin>>A[i];
		A[i]--;
		uf.merge(i,A[i]);
		indeg[A[i]]++;
	}
	{
		queue<int>Q;
		for(int i=0;i<N;i++)if(indeg[i]==0)Q.push(i);
		while(!Q.empty())
		{
			int u=Q.front();Q.pop();
			indeg[A[u]]--;
			G[A[u]].push_back(u);
			if(indeg[A[u]]==0)Q.push(A[u]);
		}
	}
	for(int i=0;i<N;i++)if(indeg[i]!=0)
	{
		assert(indeg[i]==1);
		dfs(i,i,0);
		idx[i]=-1;
	}
	for(int i=0;i<N;i++)if(idx[i]==-1)
	{
		int u=i;
		int sz=0;
		while(idx[u]==-1)
		{
			idx[u]=sz++;
			u=A[u];
		}
		assert(u==i);
		do{
			len[u]=sz;
			u=A[u];
		}while(u!=i);
	}
	cin>>Q;
	for(;Q--;)
	{
		int S,T;cin>>S>>T;S--,T--;
		if(!uf.same(S,T))
		{
			cout<<"-1\n";
			continue;
		}
		int base=-1;
		if(indeg[S]!=0)
		{
			if(indeg[T]==0)
			{
				cout<<"-1\n";
				continue;
			}
			base=idx[T]-idx[S];
			base=(base%len[S]+len[S])%len[S];
		}
		else
		{
			if(indeg[T]==0)
			{
				if(root[S]!=root[T]||depth[S]<depth[T])
				{
					cout<<"-1\n";
					continue;
				}
				int d=depth[S]-depth[T];
				int upk=d/L,lok=(d+R-1)/R;//L*k<=d, d<=R*k
				if(lok<=upk)cout<<lok<<"\n";
				else cout<<"-1\n";
				continue;
			}
			else
			{
				base=idx[T]-idx[root[S]];
				base=(base%len[T]+len[T])%len[T];
				base+=depth[S];
			}
		}
		auto fn=[&](int k){
			long dL=(long)L*k,dR=(long)R*k;
			//find x>=0 s.t. dL<=base+len[T]*x<=dR
			//find x>=0 s.t. dL-base<=len[T]*x<=dR-base
			dL-=base;dR-=base;
			if(dR<0)return false;
			else
			{
				dR/=len[T];
				return dL<=len[T]*dR;
			}
		};
		{//gutyoku
			bool ex=false;
			for(int k=1;k<=N;k++)if(fn(k))
			{
				cout<<k<<"\n";
				ex=true;
				break;
			}
			if(ex)continue;
		}
		int Lk=0,Rk=N+114514;
		while(Rk-Lk>1&&false)
		{
			int mk=(Lk+Rk)/2;
			if(fn(mk))Rk=mk;
			else Lk=mk;
		}
		if(Rk==N+114514)cout<<"-1\n";
		else cout<<Rk<<"\n";
	}
}
0