Submission #4070694
Source Code Expand
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;
typedef long long LL;
typedef vector<int> VI;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
putchar('\n');
}
int N, M;
VI G[100011];
int use[100011];
void MAIN() {
scanf("%d%d", &N, &M);
REP (i, M) {
int x, y;
scanf("%d%d", &x, &y);
x--; y--;
G[x].push_back(y);
G[y].push_back(x);
}
VI ord; ord.reserve(N);
LL S, C, B;
S=C=B=0;
REP (v, N) if (!use[v]) {
if (G[v].empty()) {
S++;
} else {
bool bipartite = true;
ord.clear();
ord.push_back(v);
use[v] = 1;
for (int i=0; i<(int)ord.size(); i++) {
int w = ord[i];
EACH (e, G[w]) {
if (use[*e] && use[*e] == use[w]) {
bipartite = false;
}
if (use[*e]) continue;
ord.push_back(*e);
use[*e] = 3 - use[w];
}
}
(bipartite? B: C)++;
}
}
LL ans = 0;
ans += S*N*2;
ans -= S*S;
ans += B*B*2;
ans += B*C*2;
ans += C*C;
printf("%lld\n", ans);
}
int main() {
int TC = 1;
// scanf("%d", &TC);
REP (tc, TC) MAIN();
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Squared Graph |
User |
natsugiri |
Language |
C++14 (GCC 5.4.1) |
Score |
800 |
Code Size |
1725 Byte |
Status |
AC |
Exec Time |
78 ms |
Memory |
7552 KB |
Compile Error
./Main.cpp: In function ‘void MAIN()’:
./Main.cpp:28:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
^
./Main.cpp:31:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
^
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 |
2560 KB |
in10.txt |
AC |
3 ms |
2560 KB |
in11.txt |
AC |
3 ms |
2560 KB |
in12.txt |
AC |
21 ms |
6016 KB |
in13.txt |
AC |
21 ms |
6144 KB |
in14.txt |
AC |
39 ms |
6144 KB |
in15.txt |
AC |
6 ms |
3328 KB |
in16.txt |
AC |
28 ms |
4608 KB |
in17.txt |
AC |
23 ms |
5376 KB |
in18.txt |
AC |
52 ms |
6144 KB |
in19.txt |
AC |
41 ms |
6016 KB |
in2.txt |
AC |
3 ms |
2560 KB |
in20.txt |
AC |
41 ms |
6144 KB |
in21.txt |
AC |
74 ms |
7552 KB |
in22.txt |
AC |
48 ms |
5504 KB |
in23.txt |
AC |
35 ms |
4736 KB |
in24.txt |
AC |
3 ms |
3068 KB |
in25.txt |
AC |
74 ms |
7552 KB |
in26.txt |
AC |
3 ms |
2560 KB |
in27.txt |
AC |
3 ms |
2688 KB |
in28.txt |
AC |
78 ms |
7552 KB |
in3.txt |
AC |
3 ms |
2560 KB |
in4.txt |
AC |
4 ms |
2560 KB |
in5.txt |
AC |
52 ms |
5632 KB |
in6.txt |
AC |
5 ms |
3328 KB |
in7.txt |
AC |
5 ms |
3072 KB |
in8.txt |
AC |
9 ms |
3840 KB |
in9.txt |
AC |
23 ms |
4352 KB |
sample1.txt |
AC |
3 ms |
2560 KB |
sample2.txt |
AC |
3 ms |
2560 KB |