第61个点一直MLE怎么回事
查看原帖
第61个点一直MLE怎么回事
744789
Big_Bishop楼主2024/7/21 20:26
#include<iostream>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
struct node{
	int cnt,len,id;
}b[200005];
bool cmp(node x,node y){
	return x.cnt!=y.cnt?x.cnt<y.cnt:x.len<y.len;
}
struct edge{
	int to,nxt;
}e[100005];
int head[100005],tot;
void add(int u,int v){
	e[++tot]={v,head[u]};
	head[u]=tot;
}
int n,m,cnt,top;
unordered_map<string,int> id;
unordered_map<string,string> d;
unordered_map<int,string> d1;
string a[100005];
bool vis[100005];
int C(string x){
	int sum=0;
	for(int i=0;i<x.size();i++){
		if(x[i]=='r') sum++;
	}
	return sum;
}
string lw(string x){
	for(int i=0;i<x.size();i++){
		if(x[i]<='Z'&&'A'<=x[i]){
			x[i]+=32;
		}
	}
	return x;
}
void dfs(int u,int f){
	if(vis[u]) return;
	vis[u]=1;
	d[d1[u]]=d1[f];
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		dfs(v,f);
	}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]=lw(a[i]);
		d[a[i]]=a[i];
	}
	cin>>m;
	while(m--){
		string x,y;
		cin>>x>>y;
		x=lw(x);
		y=lw(y);
		if(id[x]==0){
			cnt++;
		id[x]=cnt;
		}
		if(id[y]==0){
			cnt++;
		id[y]=cnt;
		}
		
		d1[id[x]]=x;
		d1[id[y]]=y;
		add(id[y],id[x]);
//		q.push({C(x),x.size(),id[x]});
//		q.push({C(y),y.size(),id[y]});
		b[++top]={C(x),x.size(),id[x]};
		b[++top]={C(y),y.size(),id[y]};
	}
	sort(b+1,b+top+1,cmp);
	for(int i=1;i<=top;i++){
		node x=b[i];
		if(vis[x.id]) continue;
		dfs(x.id,x.id);
	}
	long long ans1=0,ans2=0;
	for(int i=1;i<=n;i++){
		a[i]=d[a[i]];
		ans2+=a[i].size();
		ans1+=C(a[i]);
	}
	cout<<ans1<<" "<<ans2;
	return 0;
}
/*
1
rrr
2
rrr bbr
bbr aaaaaaa
*/
2024/7/21 20:26
加载中...