NC208166. 寻找未曾见过的你
描述
输入描述
第一行输入4个整数：n，x，y，z。分别代表次元空间的点的个数，第一个次元空间的边的数量，第二个次元空间的边的数量，第三个次元空间的边的数量。然后x行，每行2个整数：u，v。代表第一个次元的点u和点v互相连接。然后y行，每行2个整数：u，v。代表第二个次元的点u和点v互相连接。然后z行，每行2个整数：u，v。代表第三个次元的点u和点v互相连接。1<=n<=5e50<=x<=n0<=y<=n0<=z<=n1<=u<=n1<=v<=n
输出描述
输出有n行。第i行代表如果灵魂从点i苏醒，AR苏醒的方案数。
示例1
输入:
3 2 2 1 1 2 2 3 1 2 2 3 1 3
输出:
2 1 2
说明:
C++11(clang++ 3.9) 解法, 执行用时: 1524ms, 内存消耗: 82648K, 提交时间: 2020-06-25 19:08:54
#include<bits/stdc++.h>
using namespace std;
map<int,map<int,map<int,int>>>T;
int V[3][500005];
int find(int i,int a)
{
if(V[i][a]==a)return a;
return V[i][a]=find(i,V[i][a]);
}
int main()
{
int i,j,a,b,n,x,y,z;
scanf("%d%d%d%d",&n,&x,&y,&z);
for(i=1;i<=n;i++)V[0][i]=V[1][i]=V[2][i]=i;
while(x--)
{
scanf("%d%d",&i,&j);
a=find(0,i),b=find(0,j);
if(a!=b)V[0][a]=b;
}
while(y--)
{
scanf("%d%d",&i,&j);
a=find(1,i),b=find(1,j);
if(a!=b)V[1][a]=b;
}
while(z--)
{
scanf("%d%d",&i,&j);
a=find(2,i),b=find(2,j);
if(a!=b)V[2][a]=b;
}
for(i=1;i<=n;i++)x=find(0,i),y=find(1,i),z=find(2,i),T[x][y][z]++;
for(i=1;i<=n;i++)
{
x=find(0,i),y=find(1,i),z=find(2,i);
printf("%d\n",T[x][y][z]);
}
}
C++14(g++5.4) 解法, 执行用时: 1487ms, 内存消耗: 71400K, 提交时间: 2020-06-22 17:15:19
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
vector<int>adj[N];
long long type[N];
int n, m[3], u, v, space;
void DFS(int cur, int root)
{
if(type[cur]>>(20*space) & 0xfffff)
return;
type[cur] |= root * 1LL << (20*space);
for(auto r : adj[cur])
DFS(r, root);
}
int main()
{
ios::sync_with_stdio(0);
cin >> n >> m[0] >> m[1] >> m[2];
for(space = 0; space < 3; space++)
{
for(int i = 1; i <= n; i++)
adj[i].clear();
for(int i = 0; i < m[space]; i++)
{
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i = 1; i <= n; i++)
DFS(i, i);
}
map<long long, int>mp;
for(int i = 1; i <= n; i++)
mp[type[i]]++;
for(int i = 1; i <= n; i++)
cout << mp[type[i]] << endl;
}