社区讨论

求助,开不开O2都RE,85pts

P8403[CCC 2022 J4] Good Groups参与者 3已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@lor3l68q
此快照首次捕获于
2023/11/09 19:20
2 年前
此快照最后确认于
2023/11/09 20:53
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
#define itn int
#define ll long long
using namespace std;
const int N=1e5+10;
const int M=1e2;
int n,m,q;
int fa[N];
int tim;
ll ans;
string s1[N][5],s2[N][5];

map <string, int> mp;
int Find(int x){
	if(fa[x]==x) return x;
	return fa[x]=Find(fa[x]);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		s1[i][1].resize(M);
		s1[i][2].resize(M);
		scanf("%s %s",&s1[i][1][0],&s1[i][2][0]);
		if(mp[s1[i][1]]==0){
			mp[s1[i][1]]=++tim;
		}if(mp[s1[i][2]]==0){
			mp[s1[i][2]]=++tim;
		}
//		cout<<s1[i][1]<<"\n"<<s1[i][2];
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		s2[i][1].resize(M);
		s2[i][2].resize(M);
		scanf("%s %s",&s2[i][1][0],&s2[i][2][0]);
		if(mp[s2[i][1]]==0){
			mp[s2[i][1]]=++tim;
		}if(mp[s2[i][2]]==0){
			mp[s2[i][2]]=++tim;
		}
	}
	cin>>q;
	for(int i=1;i<=tim;i++){
		fa[i]=i;
	}
	for(int i=1;i<=q;i++){
		string c,c1,c2;
		c.resize(M);c1.resize(M);c2.resize(M);
		scanf("%s %s %s",&c[0],&c1[0],&c2[0]);
//		cout<<c<<" "<<c1<<" "<<c2<<"\n";
		if(mp[c]==0){
			mp[c]=++tim;
			fa[tim]=tim;
		}if(mp[c1]==0){
			mp[c1]=++tim;
			fa[tim]=tim;
		}if(mp[c2]==0){
			mp[c2]=++tim;
			fa[tim]=tim;
		}
		int xx=Find(mp[c]);	
		int yy=Find(mp[c1]);	
		int zz=Find(mp[c2]);				
		fa[zz]=fa[yy]=xx;
	}
	for(int i=1;i<=n;i++){
		if(fa[ Find(mp[s1[i][1]]) ]!=fa[ Find(mp[s1[i][2]]) ] ){
			ans++;
		}
	}
	for(int i=1;i<=m;i++){
		if(fa[mp[s2[i][1]]]==fa[mp[s2[i][2]]]){
			ans++;
		}
	}
	cout<<ans;
	return 0;
}

回复

7 条回复,欢迎继续交流。

正在加载回复...