105332024-04-04 17:46:41111Kutyavetélkedő 2cpp17Időlimit túllépés 21/1001.282s123696 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long

void scc_dfs(const auto&g,auto&v,auto&s,int i){
	if(v[i]){
		return;
	}
	v[i]=1;
	for(int j:g[i]){
		scc_dfs(g,v,s,j);
	}
	s.push_back(i);
}

int scc(const auto&g,const auto&gg,auto&c){
	int n=g.size();
	vector<int>v,s;
	v.assign(n,0);
	for(int i=0;i<n;i++){
		scc_dfs(g,v,s,i);
	}
	v.assign(n,0);
	for(int i=n-1;i>=0;i--){
		if(v[s[i]]){
			continue;
		}
		c.emplace_back();
		scc_dfs(gg,v,c.back(),s[i]);
	}
	return c.size();
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,K;
	cin>>N>>K;
	vector<int>v(N);
	for(int i=0;i<N;i++){
		cin>>v[i];
	}
	int M;
	cin>>M;
	vector<vector<int>>g(K+1),gg(K+1);
	for(int i=0;i<M;i++){
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		gg[b].push_back(a);
	}
	vector<vector<int>>c;
	int O=scc(g,gg,c);
	vector<int>cc(K+1);
	for(int i=0;i<O;i++){
		for(int j:c[i]){
			cc[j]=i;
		}
	}
	vector<vector<int>>h(O);
	for(int i=0;i<O;i++){
		for(int j:c[i]){
			for(int k:g[j]){
				int l=cc[k];
				if(l!=i){
					h[i].push_back(l);
				}
			}
		}
	}
	for(int i=0;i<O;i++){
		sort(h[i].begin(),h[i].end());
		h[i].erase(unique(h[i].begin(),h[i].end()),h[i].end());
	}
	for(int i=1;i<=K;i++){
		sort(g[i].begin(),g[i].end());
	}
	int ans=2;
	int last=cc[v[0]];
	for(int i=0;i+1<N;i++){
		if(binary_search(g[v[i]].begin(),g[v[i]].end(),v[i+1])){
			ans+=2;
			continue;
		}
		int next=cc[v[i+1]];
		vector<int>w(O);
		deque<int>q;
		w[last]=1;
		q.push_back(last);
		while(!q.empty()&&last!=next){
			int i=q.front();
			q.pop_front();
			for(int j:h[i]){
				if(w[j]){
					continue;
				}
				w[j]=1;
				q.push_back(j);
				if(j==next){
					last=j;
					break;
				}
			}
		}
		if(last!=next){
			break;
		}
		ans+=1;
	}
	cout<<ans<<'\n';
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1700 KiB
2Elfogadva3ms1876 KiB
subtask221/21
3Elfogadva3ms2240 KiB
4Elfogadva3ms2452 KiB
5Elfogadva3ms2408 KiB
6Elfogadva3ms2560 KiB
7Elfogadva3ms2876 KiB
8Elfogadva3ms2952 KiB
9Elfogadva3ms2836 KiB
subtask30/45
10Elfogadva287ms16268 KiB
11Elfogadva180ms16496 KiB
12Időlimit túllépés1.268s16364 KiB
13Időlimit túllépés1.259s16520 KiB
14Időlimit túllépés1.268s16356 KiB
15Időlimit túllépés1.271s16400 KiB
16Időlimit túllépés1.256s18420 KiB
17Időlimit túllépés1.282s20444 KiB
18Időlimit túllépés1.279s21644 KiB
19Időlimit túllépés1.264s21648 KiB
20Elfogadva1.187s40512 KiB
subtask40/34
21Időlimit túllépés1.261s29688 KiB
22Időlimit túllépés1.24s39004 KiB
23Időlimit túllépés1.266s48648 KiB
24Elfogadva342ms123696 KiB
25Időlimit túllépés1.266s48672 KiB
26Időlimit túllépés1.269s38920 KiB