結果

問題 No.2704 L to R Graph
コンテスト
ユーザー kotatsugame
提出日時 2024-03-29 23:35:38
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 573 ms / 3,000 ms
コード長 3,421 bytes
コンパイル時間 1,732 ms
コンパイル使用メモリ 97,336 KB
実行使用メモリ 24,880 KB
最終ジャッジ日時 2024-09-30 17:04:20
合計ジャッジ時間 8,984 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<queue>
#include<cassert>
#include<atcoder/dsu>
#include<atcoder/math>
using namespace std;
#include<vector>
struct LCA{
	int N;
	vector<vector<int> >G,parent;
	vector<int>depth;
	LCA(int N_=0):N(N_),G(N_),depth(N_)
	{
		int lg=0;
		while((1<<lg)+1<N_)lg++;
		parent.assign(lg+1,vector<int>(N_));
	}
	void add_edge(int u,int v)
	{
		G[u].push_back(v);
		G[v].push_back(u);
	}
	void dfs(int u,int p,int d)
	{
		depth[u]=d;
		parent[0][u]=p;
		for(int v:G[u])if(v!=p)dfs(v,u,d+1);
	}
	void build(int root=0)
	{
		dfs(root,-1,0);
		for(int k=1;k<parent.size();k++)
		{
			for(int i=0;i<N;i++)
			{
				if(parent[k-1][i]==-1)parent[k][i]=-1;
				else parent[k][i]=parent[k-1][parent[k-1][i]];
			}
		}
	}
	int lca(int u,int v)
	{
		if(depth[u]>depth[v])swap(u,v);
		for(int k=0;k<parent.size();k++)if(depth[v]-depth[u]>>k&1)v=parent[k][v];
		if(u==v)return u;
		for(int k=parent.size();k--;)if(parent[k][u]!=parent[k][v])
		{
			u=parent[k][u];
			v=parent[k][v];
		}
		return parent[0][u];
	}
	int dist(int u,int v)
	{
		int w=lca(u,v);
		return depth[u]+depth[v]-2*depth[w];
	}
};
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;
	LCA lca(N+1);
	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);
			lca.add_edge(A[u],u);
			if(indeg[A[u]]==0)Q.push(A[u]);
		}
	}
	for(int i=0;i<N;i++)if(indeg[i]!=0)
	{
		lca.add_edge(N,i);
		assert(indeg[i]==1);
		dfs(i,i,0);
		idx[i]=-1;
	}
	lca.build(N);
	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(lca.lca(S,T)!=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];
			}
		}
		int lok=(base+R-1)/R;//Rk>=base
		/*
		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<=5000;k++)if(fn(k))
			{
				cout<<k<<"\n";
				ex=true;
				break;
			}
			if(ex)continue;
		}
		*/
		int Lk=lok-1,Rk=N+114514;
		while(Rk-Lk>1)
		{
			int mk=(Lk+Rk)/2;
			if(atcoder::floor_sum(mk-lok+1,len[T],R,(long)R*lok-base)>
				atcoder::floor_sum(mk-lok+1,len[T],L,(long)L*lok-base-1))Rk=mk;
			else Lk=mk;
		}
		if(Rk==N+114514)cout<<"-1\n";
		else cout<<Rk<<"\n";
	}
}
0