记录编号	432022	评测结果	AAAAAAAAAA
题目名称	膜法师	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	0.984 s
提交时间	2017-08-02 18:29:52	内存使用	51.81 MiB

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>

#include<cstdlib>   //手动开栈真恶心= = 
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
int n;
struct edge{
	int s,e,n;
}a[1000001];
int pre[1000001],tot;
inline void insert(int s,int e){
	a[++tot].s=s;
	a[tot].e=e;
	a[tot].n=pre[s];
	pre[s]=tot;
}
inline int my_max(int a,int b){
	return a>b?a:b;
}
inline int my_min(int a,int b){
	return a<b?a:b;
}
struct node{
	int id;
}hh[1000001];
bool die[1000001];
int target[1000001];
int ans_min(0),ans_max(0);
int in[1000001];
int low[1000001],dfn[1000001],zhan[1000001],bl[1000001],size[1000001];
int cnt,top,qlt;
bool vis[1000001];
int cl[1000001];
inline void tarjan(int u){
	dfn[u]=low[u]=++cnt;
	zhan[++top]=u;
	vis[u]=1;
	for(int i=pre[u];i!=-1;i=a[i].n){
		int e(a[i].e);
		if(!dfn[e]){
			tarjan(e);
			low[u]=my_min(low[u],low[e]);
		}
		else
			if(vis[e])
				low[u]=my_min(low[u],dfn[e]);
	}
	if(low[u]==dfn[u]){
		qlt++;
		while(1){
			int tmp(zhan[top--]);
			bl[tmp]=qlt;
			vis[tmp]=0;
			size[qlt]++;
			if(tmp==u)
				break;
		}
	}
}
inline bool cmp(node a,node b){
	if(cl[bl[a.id]]==cl[bl[b.id]])
		return in[a.id]<in[b.id];
	return cl[bl[a.id]]<cl[bl[b.id]];
}
queue<int>q;
int now(0x7fffffff),inf(0x7fffffff),fir;
int main(){
	freopen("maf.in","r",stdin);
	freopen("maf.out","w",stdout);
	
	int __size__=128<<20;
	char *__p__ =(char*)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__p__));
	
	memset(pre,-1,sizeof(pre));
	n=read();
	for(int i=1;i<=n;i++){
		hh[i].id=i;
		target[i]=read();
		if(target[i]==i){
			die[i]=1;
			bl[i]=++qlt;
			cl[qlt]=0;
			size[qlt]=1;
			ans_max++,ans_min++;
		}
	}
	for(int i=1;i<=n;i++){
		if(!die[i]&&!die[target[i]])
			insert(i,target[i]),in[target[i]]++;
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i]&&!die[i])
			tarjan(i);
	for(int i=1;i<=tot;i++){
		int s(a[i].s),e(a[i].e);
		s=bl[s],e=bl[e];
		if(s!=e)
			cl[s]=cl[e]=1;
	}
	for(int i=1;i<=qlt;i++){
		if(cl[i]==0&&size[i]>1){
			ans_max+=size[i]-1;
			ans_min+=(size[i]+1)>>1;
		}
	}
	sort(hh+1,hh+1+n,cmp);
	for(int i=1;i<=n;i++){
		int tmp(hh[i].id);
		if(cl[bl[tmp]]==1&&!in[tmp]){
			now=my_min(now,i);
			continue;
		}
		if(cl[bl[tmp]]==1&&in[tmp]){
			fir=i;
			break;
		}
	}
	if(now!=inf){
		ans_max+=n-fir+1;
		for(int i=now;i<fir;i++)
			q.push(hh[i].id);
		while(!q.empty()){
			int k(q.front());
			cl[bl[k]]=0;
			q.pop();
			int tar(target[k]);
			if(!die[tar]){
				die[tar]=1;
				cl[bl[tar]]=0;
				ans_min++;
				int kk(target[tar]);
				in[kk]--;
				if(!die[kk]&&!in[kk])
					q.push(kk);
			}
		}
	}
	for(int i=1;i<=cnt;i++)
		if(cl[i])
			ans_min+=(size[i]+1)>>1;
	printf("%d %d",ans_min,ans_max);
}