#1015540 (C++17) No.2704 L to R Graph

提出ソース

結果

問題	No.2704 L to R Graph
ユーザー	lgswdn
提出日時	2024-10-04 23:20:26
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	2,966 bytes
コンパイル時間	1,994 ms
コンパイル使用メモリ	214,676 KB
実行使用メモリ	27,592 KB
最終ジャッジ日時	2024-10-04 23:20:32
合計ジャッジ時間	4,839 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	4 ms 15,508 KB
testcase_01	AC	4 ms 15,616 KB
testcase_02	AC	4 ms 15,016 KB
testcase_03	AC	5 ms 15,088 KB
testcase_04	AC	5 ms 16,000 KB
testcase_05	AC	4 ms 15,452 KB
testcase_06	AC	4 ms 15,748 KB
testcase_07	AC	4 ms 18,792 KB
testcase_08	AC	43 ms 21,124 KB
testcase_09	AC	56 ms 21,144 KB
testcase_10	AC	42 ms 20,996 KB
testcase_11	AC	38 ms 25,416 KB
testcase_12	AC	38 ms 25,600 KB
testcase_13	AC	36 ms 25,056 KB
testcase_14	AC	39 ms 25,412 KB
testcase_15	AC	37 ms 25,412 KB
testcase_16	AC	38 ms 25,284 KB
testcase_17	AC	37 ms 25,668 KB
testcase_18	AC	35 ms 25,652 KB
testcase_19	AC	37 ms 25,024 KB
testcase_20	AC	37 ms 25,416 KB
testcase_21	RE	-
testcase_22	RE	-
testcase_23	AC	48 ms 26,692 KB
testcase_24	AC	54 ms 26,948 KB
testcase_25	AC	48 ms 27,588 KB
testcase_26	AC	49 ms 27,592 KB
testcase_27	AC	32 ms 21,620 KB
testcase_28	AC	33 ms 21,196 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

//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); if(r-w+1<=m) 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;
}

yukicoder

結果

テストケース

ソースコード