結果
| 問題 | No.2704 L to R Graph |
| ユーザー |
 Rubikun
|
| 提出日時 | 2024-03-29 22:41:58 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 692 ms / 3,000 ms |
| コード長 | 6,921 bytes |
| コンパイル時間 | 2,395 ms |
| コンパイル使用メモリ | 211,272 KB |
| 最終ジャッジ日時 | 2025-02-20 15:21:07 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }#define all(x) (x).begin(),(x).end()#define fi first#define se second#define mp make_pair#define si(x) int(x.size())const int mod=998244353,MAX=300005,INF=1<<30;// crt + floor_sum//https://github.com/atcoder/ac-library/releases/tag/v1.4constexpr long long safe_mod(long long x, long long m) {x %= m;if (x < 0) x += m;return x;}constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {a = safe_mod(a, b);if (a == 0) return {b, 0};long long s = b, t = a;long long m0 = 0, m1 = 1;while (t) {long long u = s / t;s -= t * u;m0 -= m1 * u;auto tmp = s;s = t;t = tmp;tmp = m0;m0 = m1;m1 = tmp;}if (m0 < 0) m0 += b / s;return {s, m0};}std::pair<long long, long long> crt(const std::vector<long long>& r,const std::vector<long long>& m) {assert(r.size() == m.size());int n = int(r.size());long long r0 = 0, m0 = 1;for (int i = 0; i < n; i++) {assert(1 <= m[i]);long long r1 = safe_mod(r[i], m[i]), m1 = m[i];if (m0 < m1) {std::swap(r0, r1);std::swap(m0, m1);}if (m0 % m1 == 0) {if (r0 % m1 != r1) return {0, 0};continue;}long long g, im;std::tie(g, im) = inv_gcd(m0, m1);long long u1 = (m1 / g);if ((r1 - r0) % g) return {0, 0};long long x = (r1 - r0) / g % u1 * im % u1;r0 += x * m0;m0 *= u1;if (r0 < 0) r0 += m0;}return {r0, m0};}unsigned long long floor_sum_unsigned(unsigned long long n,unsigned long long m,unsigned long long a,unsigned long long b) {unsigned long long ans = 0;while (true) {if (a >= m) {ans += n * (n - 1) / 2 * (a / m);a %= m;}if (b >= m) {ans += n * (b / m);b %= m;}unsigned long long y_max = a * n + b;if (y_max < m) break;n = (unsigned long long)(y_max / m);b = (unsigned long long)(y_max % m);std::swap(m, a);}return ans;}long long floor_sum(long long n, long long m, long long a, long long b) {assert(0 <= n && n < (1LL << 32));assert(1 <= m && m < (1LL << 32));unsigned long long ans = 0;if (a < 0) {unsigned long long a2 = safe_mod(a, m);ans -= 1ULL * n * (n - 1) / 2 * ((a2 - a) / m);a = a2;}if (b < 0) {unsigned long long b2 = safe_mod(b, m);ans -= 1ULL * n * ((b2 - b) / m);b = b2;}return ans + floor_sum_unsigned(n, m, a, b);}ll gcd(ll a,ll b){if(b==0) return a;return gcd(b,a%b);}struct UF{int n;vector<int> par,size,edge;void init(int n_){n=n_;par.assign(n,-1);size.assign(n,1);edge.assign(n,0);for(int i=0;i<n;i++){par[i]=i;}}int root(int a){if(par[a]==a) return a;else return par[a]=root(par[a]);}void unite(int a,int b){edge[root(a)]++;if(root(a)!=root(b)){size[root(a)]+=size[root(b)];edge[root(a)]+=edge[root(b)];par[root(b)]=root(a);}}bool check(int a,int b){return root(a)==root(b);}};vector<int> G[MAX];ll bel[MAX],pos[MAX],depth[MAX],ro[MAX],sz[MAX],par[18][MAX];void DFS(int u,int p,int roro){ro[u]=roro;par[0][u]=p;for(int to:G[u]){depth[to]=depth[u]+1;DFS(to,u,roro);}}int main(){std::ifstream in("text.txt");std::cin.rdbuf(in.rdbuf());cin.tie(0);ios::sync_with_stdio(false);ll N,L,R;cin>>N>>L>>R;vector<int> A(N);vector<int> deg(N);for(int i=0;i<N;i++){cin>>A[i];A[i]--;deg[A[i]]++;}queue<int> Q;for(int i=0;i<N;i++){if(deg[i]==0) Q.push(i);}while(!Q.empty()){int u=Q.front();Q.pop();G[A[u]].push_back(u);deg[A[u]]--;if(deg[A[u]]==0) Q.push(A[u]);}UF uf;uf.init(N);for(int i=0;i<N;i++){if(deg[i]){uf.unite(i,A[i]);}}for(int t=0;t<18;t++) for(int i=0;i<N;i++) par[t][i]=-1;for(int i=0;i<N;i++){if(deg[i]){bel[i]=uf.root(i);if(uf.root(i)==i){vector<int> X;int now=i;while(1){X.push_back(now);now=A[now];if(now==i) break;}for(int t=0;t<si(X);t++){pos[X[t]]=t;sz[X[t]]=si(X);}}DFS(i,-1,i);}}for(int t=1;t<=17;t++){for(int i=0;i<N;i++){if(par[t-1][i]==-1) continue;par[t][i]=par[t-1][par[t-1][i]];}}int QQ;cin>>QQ;while(QQ--){int s,t;cin>>s>>t;s--;t--;int ss=ro[s],tt=ro[t];if(depth[t]==0){if(bel[ss]!=bel[tt]){cout<<-1<<"\n";continue;}ll a,b;b=(pos[tt]-pos[ss]+sz[ss])%sz[ss];b+=depth[s];a=sz[ss];//cout<<a<<" "<<b<<endl;ll ne=(b+R-1)/R;ll left=ne-1,right=2*N;while(right-left>1){ll mid=(left+right)/2;ll sum=floor_sum(mid+1,a,R,-b)-floor_sum(mid+1,a,L,-b-1);sum-=floor_sum(ne,a,R,-b)-floor_sum(ne,a,L,-b-1);if(sum>0) right=mid;else left=mid;}if(right==2*N) cout<<-1<<"\n";else cout<<right<<"\n";}else{if(ss!=tt||depth[s]<depth[t]){cout<<-1<<"\n";continue;}int kyo=depth[s]-depth[t];int now=s;for(int q=17;q>=0;q--){if(kyo&(1<<q)){now=par[q][now];}}if(now==t){ll x=kyo;ll K=(x+R-1)/R;if(K*L<=x&&x<=K*R) cout<<K<<"\n";else cout<<-1<<"\n";}else{cout<<-1<<"\n";}}}}