社区讨论
求助,开不开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 条回复,欢迎继续交流。
正在加载回复...