Submission #1866980
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount
#define INF INT_MAX/3
struct UnionFind{
vector<int> v;
UnionFind(int n) : v(n, -1) {}
void init(){ for(int i = 0;i < v.size();i++)v[i]=-1; }
int find(int x) { return v[x] < 0 ? x : v[x] = find(v[x]); }
bool unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return false;
if (-v[x] < -v[y]) swap(x, y);
v[x] += v[y]; v[y] = x;
return true;
}
bool root(int x) { return v[x] < 0; }
bool same(int x, int y) { return find(x) == find(y); }
int size(int x) { return -v[find(x)]; }
};
ll n,m;
ll cnt[3];
bool used[202020];
ll c[202020];
vector<ll> g[202020];
bool dfs(ll v,ll nc){
c[v]=nc;
for(ll nv : g[v]){
if(c[nv]==-1&&!dfs(nv,1-nc))return false;
else{
if(c[nv]==nc)return false;
}
}
return true;
}
int main(){
cin>>n>>m;
UnionFind uf(n);
rep(i,m){
ll a,b;
cin>>a>>b;
a--; b--;
uf.unite(a,b);
g[a].push_back(b);
g[b].push_back(a);
}
memset(c,-1,sizeof(c));
rep(i,n){
if(used[uf.find(i)])continue;
used[uf.find(i)]=true;
if(uf.size(i)==1)cnt[2]++;
else{
bool nibu=dfs(i,0);
cnt[nibu]++;
}
}
ll res=cnt[2]*n*2-cnt[2]*cnt[2];
res+=(cnt[0]+cnt[1])*(cnt[0]+cnt[1]);
res+=cnt[1]*cnt[1];
cout<<res<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Squared Graph |
User |
yamad |
Language |
C++14 (GCC 5.4.1) |
Score |
800 |
Code Size |
1963 Byte |
Status |
AC |
Exec Time |
155 ms |
Memory |
13312 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
800 / 800 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample1.txt, sample2.txt |
All |
sample1.txt, sample2.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in3.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt |
Case Name |
Status |
Exec Time |
Memory |
in1.txt |
AC |
3 ms |
6528 KB |
in10.txt |
AC |
3 ms |
7040 KB |
in11.txt |
AC |
3 ms |
6528 KB |
in12.txt |
AC |
40 ms |
10112 KB |
in13.txt |
AC |
40 ms |
10240 KB |
in14.txt |
AC |
76 ms |
10240 KB |
in15.txt |
AC |
10 ms |
7424 KB |
in16.txt |
AC |
58 ms |
9472 KB |
in17.txt |
AC |
43 ms |
9600 KB |
in18.txt |
AC |
102 ms |
11264 KB |
in19.txt |
AC |
76 ms |
10624 KB |
in2.txt |
AC |
3 ms |
6528 KB |
in20.txt |
AC |
83 ms |
10624 KB |
in21.txt |
AC |
155 ms |
13312 KB |
in22.txt |
AC |
112 ms |
12032 KB |
in23.txt |
AC |
91 ms |
11008 KB |
in24.txt |
AC |
4 ms |
7040 KB |
in25.txt |
AC |
149 ms |
13312 KB |
in26.txt |
AC |
3 ms |
6528 KB |
in27.txt |
AC |
3 ms |
6656 KB |
in28.txt |
AC |
147 ms |
13312 KB |
in3.txt |
AC |
3 ms |
6528 KB |
in4.txt |
AC |
3 ms |
6528 KB |
in5.txt |
AC |
116 ms |
11520 KB |
in6.txt |
AC |
8 ms |
7296 KB |
in7.txt |
AC |
8 ms |
7296 KB |
in8.txt |
AC |
16 ms |
7936 KB |
in9.txt |
AC |
46 ms |
8960 KB |
sample1.txt |
AC |
3 ms |
6528 KB |
sample2.txt |
AC |
3 ms |
6528 KB |