104502024-04-02 20:22:48111Gossip Spreadingcpp17Elfogadva 100/10083ms10508 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N;
	cin>>N;
	vector<int>p(N);
	for(int i=0;i<N;i++){
		cin>>p[i];
	}
	vector<int>v(N),c(N),d(N+1);
	int x=0;
	for(int i=0;i<N;i++){
		if(v[i]){
			continue;
		}
		v[i]=++x;
		int dd=1;
		for(int j=p[i];j!=i;j=p[j]){
			v[j]=x;
			c[j]=dd++;
		}
		d[v[i]]=dd;
	}
	int Q;
	cin>>Q;
	while(Q--){
		int a,b;
		cin>>a>>b;
		if(v[a]!=v[b]){
			cout<<-1<<' ';
			continue;
		}
		if(c[a]>c[b]){
			swap(a,b);
		}
		cout<<min(c[b]-c[a],c[a]-c[b]+d[v[a]])<<' ';
	}
	cout<<'\n';
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1828 KiB
2Elfogadva3ms2016 KiB
subtask230/30
3Elfogadva3ms2116 KiB
4Elfogadva3ms2484 KiB
5Elfogadva3ms2696 KiB
6Elfogadva3ms2908 KiB
7Elfogadva3ms3124 KiB
8Elfogadva3ms3332 KiB
9Elfogadva3ms3200 KiB
10Elfogadva3ms3252 KiB
11Elfogadva3ms3200 KiB
12Elfogadva3ms3200 KiB
subtask350/50
13Elfogadva64ms3856 KiB
14Elfogadva63ms3936 KiB
15Elfogadva63ms3940 KiB
16Elfogadva64ms3996 KiB
17Elfogadva63ms4028 KiB
18Elfogadva64ms4180 KiB
19Elfogadva64ms4268 KiB
20Elfogadva64ms4444 KiB
21Elfogadva63ms4452 KiB
22Elfogadva61ms4552 KiB
subtask420/20
23Elfogadva63ms4760 KiB
24Elfogadva83ms10232 KiB
25Elfogadva82ms10236 KiB
26Elfogadva83ms10384 KiB
27Elfogadva83ms10388 KiB
28Elfogadva82ms10376 KiB
29Elfogadva82ms10356 KiB
30Elfogadva79ms9232 KiB
31Elfogadva82ms9932 KiB
32Elfogadva83ms10508 KiB