Submission #1357826
Source Code Expand
#include <iostream> #include <vector> using namespace std; long long ans; int N, M; vector <int> G[100005]; int Colour[100005], cnt; bool ok = 1; void Read() { cin >> N >> M; for(int i = 1; i <= M; i++) { int x, y; cin >> x >> y; G[x].push_back(y); G[y].push_back(x); } } void DFS(int node, int colour) { Colour[node] = colour; ++cnt; for(int i = 0; i < G[node].size(); i++) { int neighb = G[node][i]; if(Colour[neighb] == 0) { DFS(neighb, 3 - colour); } else { if(Colour[neighb] == colour) ok = 0; } } } void Solve() { long long odd = 0, even = 0, isolate = 0; for(int i = 1; i <= N; i++) { ok = 1; cnt = 0; if(Colour[i] == 0) { DFS(i, 1); if(cnt == 1) { ++isolate; continue; } if(ok == 0) odd++; else even++; } } ans += even * 2 + odd; ans += odd * (odd - 1); ans += 2 * even * (even - 1); ans += 2 * even * odd; ans += isolate * (N - 1) * 2 + isolate; ans -= isolate * (isolate - 1); cout << ans << "\n"; } int main() { Read(); Solve(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - Squared Graph |
User | alex99 |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 1424 Byte |
Status | AC |
Exec Time | 187 ms |
Memory | 9984 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 | 2 ms | 2560 KB |
in10.txt | AC | 3 ms | 2944 KB |
in11.txt | AC | 2 ms | 2560 KB |
in12.txt | AC | 47 ms | 6016 KB |
in13.txt | AC | 47 ms | 6144 KB |
in14.txt | AC | 89 ms | 6144 KB |
in15.txt | AC | 10 ms | 3328 KB |
in16.txt | AC | 67 ms | 4608 KB |
in17.txt | AC | 51 ms | 5632 KB |
in18.txt | AC | 123 ms | 7040 KB |
in19.txt | AC | 94 ms | 7040 KB |
in2.txt | AC | 2 ms | 2560 KB |
in20.txt | AC | 93 ms | 7040 KB |
in21.txt | AC | 183 ms | 9984 KB |
in22.txt | AC | 135 ms | 5888 KB |
in23.txt | AC | 112 ms | 4864 KB |
in24.txt | AC | 3 ms | 2944 KB |
in25.txt | AC | 180 ms | 9984 KB |
in26.txt | AC | 2 ms | 2560 KB |
in27.txt | AC | 3 ms | 2688 KB |
in28.txt | AC | 187 ms | 9984 KB |
in3.txt | AC | 2 ms | 2560 KB |
in4.txt | AC | 3 ms | 2560 KB |
in5.txt | AC | 138 ms | 5632 KB |
in6.txt | AC | 8 ms | 3328 KB |
in7.txt | AC | 9 ms | 3200 KB |
in8.txt | AC | 17 ms | 3840 KB |
in9.txt | AC | 55 ms | 4992 KB |
sample1.txt | AC | 2 ms | 2560 KB |
sample2.txt | AC | 2 ms | 2560 KB |