結果

問題 No.2704 L to R Graph
ユーザー 👑 kmjpkmjp
提出日時 2024-04-10 00:13:09
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,304 bytes
コンパイル時間 2,877 ms
コンパイル使用メモリ 217,748 KB
実行使用メモリ 54,004 KB
最終ジャッジ日時 2024-04-10 00:13:24
合計ジャッジ時間 10,570 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
38,508 KB
testcase_01 WA -
testcase_02 AC 10 ms
38,508 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 287 ms
45,944 KB
testcase_09 WA -
testcase_10 AC 319 ms
45,848 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 213 ms
47,056 KB
testcase_28 AC 182 ms
42,044 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define FORR2(x,y,arr) for(auto& [x,y]:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
template<class T> bool chmax(T &a, const T &b) { if(a<b){a=b;return 1;}return 0;}
template<class T> bool chmin(T &a, const T &b) { if(a>b){a=b;return 1;}return 0;}
//-------------------------------------------------------


template<int NV> struct FunctionGraph {
	int E[NV];
	int N;
	int NG;
	int nex[61][NV];  // 2^i先の点
	vector<int> RE[NV]; // 逆向き辺
	vector<int> G[NV]; // 閉路
	int GS[NV]; // 閉路長
	int Gid[NV],Gindex[NV]; // 閉路IDとその中のindex。閉路外の場合、閉路IDは最寄りの閉路だがindexは-1
	int GV[NV], D[NV]; //最寄りの閉路の点とそこまでの距離
	void dfs(int cur,int id,int d) {
		GV[cur]=id;
		Gid[cur]=Gid[id];
		D[cur]=d;
		FORR(e,RE[cur]) if(Gindex[e]==-1) dfs(e,id,d+1);
	}
	int move(int cur,ll step) { // step先に進む
		int i;
		FOR(i,60) if(step&(1LL<<i)) cur=nex[i][cur];
		return cur;
	}
	void build(int N_) {
		N=N_;
		int i,j;
		vector<int> in(N);
		FOR(i,N) {
			RE[i].clear();
			G[i].clear();
			Gindex[i]=-2;
			nex[0][i]=E[i];
		}
		NG=0;
		FOR(i,N) {
			RE[E[i]].push_back(i);
			in[E[i]]++;
		}
		queue<int> Q;
		FOR(i,N) if(in[i]==0) Q.push(i);
		while(Q.size()) {
			int cur=Q.front();
			Q.pop();
			Gindex[cur]=-1;
			if(--in[E[cur]]==0) Q.push(E[cur]);
		}
		FOR(i,N) if(Gindex[i]==-2) {
			G[NG].push_back(i);
			while(1) {
				int x=G[NG].back();
				Gid[x]=NG;
				Gindex[x]=G[NG].size()-1;
				x=E[x];
				if(x==G[NG][0]) break;
				G[NG].push_back(x);
			}
			GS[NG]=G[NG].size();
			NG++;
		}
		FOR(i,N) if(Gindex[i]>=0) dfs(i,i,0);
		FOR(j,60) FOR(i,N) nex[j+1][i]=nex[j][nex[j][i]];
	}
};

int N,L,R;
FunctionGraph<101010> fg;
map<int,int> maxd;
map<int,int> did;
int Q,S[101010],T[101010],B[101010];
int ret[101010];
vector<int> cand[101010];

int dp[101010];
int tar[101010];
int cur[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L>>R;
	FOR(i,N) {
		cin>>fg.E[i];
		fg.E[i]--;
	}
	fg.build(N);
	
	cin>>Q;
	FOR(i,Q) {
		cin>>S[i]>>T[i];
		S[i]--,T[i]--;
		ret[i]=-1;
		if(fg.Gid[S[i]]!=fg.Gid[T[i]] || fg.D[S[i]]<fg.D[T[i]]) {
			continue;
		}
		else {
			x=fg.D[S[i]];
			y=fg.D[T[i]];
			if(y) {
				if(fg.move(S[i],x-y)!=T[i]) continue;
				int step=(y-x+R-1)/R;
				if(step*L<=y-x&&y-x<=step*R) {
					ret[i]=step;
				}
			}
			else {
				ret[i]=0;
				B[i]=x+fg.Gindex[T[i]]-fg.Gindex[S[i]];
				if(fg.Gindex[S[i]]>fg.Gindex[T[i]]) B[i]+=fg.GS[fg.Gid[S[i]]];
				cand[fg.GS[fg.Gid[S[i]]]].push_back(i);
			}
		}
	}
	FOR(i,N+1) if(cand[i].size()) {
		set<int> alive,alivep;
		FOR(j,N+1) {
			dp[j]=1<<30;
			tar[j%i]=j;
			cur[j]=-1;
			if(j) {
				alive.insert(j);
				alivep.insert(j%i);
				alivep.insert(j%i+N);
			}
		}
		dp[0]=0;
		deque<int> Q;
		Q.push_front(0);
		while(Q.size()) {
			int cur=Q.front();
			Q.pop_front();
			
			if(cur>=i&&dp[cur-i]==1<<30) {
				dp[cur-i]=dp[cur];
				alive.erase(cur-i);
				Q.push_front(cur-i);
			}
			
			auto it=alive.lower_bound(cur+L);
			while(it!=alive.end()&&*it<=cur+R) {
				dp[*it]=dp[cur]+1;
				Q.push_back(*it);
				it=alive.erase(it);
			}
			int CL=cur+L;
			int CR=cur+R+1;
			if(CL<=N) CL=N+1;
			if(CR-CL>=i) {
				FORR(j,alivep) if(j<N) {
					for(x=j;x<=N;x+=i) if(alive.count(x)) {
						dp[x]=dp[cur]+1;
						Q.push_back(x);
						alive.erase(x);
					}
				}
				alivep.clear();
			}
			else if(CL<CR) {
				CL%=N;
				CR%=N;
				if(CR<CL) CR+=N;
				while(1) {
					auto it=alivep.lower_bound(CL);
					if(it==alivep.end()||*it<CR) break;
					y=*it%N;
					for(x=y;x<=N;x+=i) if(alive.count(x)) {
						dp[x]=dp[cur]+1;
						Q.push_back(x);
						alive.erase(x);
					}
					alivep.erase(y);
					alivep.erase(y+N);
				}
			}
		}
		FORR(q,cand[i]) {
			ret[q]=dp[B[q]];
		}
		
	}
	FOR(i,Q) cout<<ret[i]<<endl;
	
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}
0