Submission #8561226


Source Code Expand

Copy
#include <iostream>
#include <vector>
using namespace std;

int dfs(const vector<vector<int>> &G, int v, vector<int> &C){
  int c = C[v], ret = 1;
  for(auto v_ : G[v]){
    if(C[v_] < 0){
      C[v_] = 1-c;
      ret &= dfs(G,v_,C);
    }else if(C[v_] == c){
      ret = 0;
    }
  }
  return ret;
}

int main(){
  long long N, M;
  cin >> N >> M;
  vector<vector<int>> G(N);
  for(int i = 0; i < M; ++i){
    int u, v;
    cin >> u >> v;
    --u, --v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  vector<int> C(N,-1);
  long long x = 0, y = 0, z = 0;
  for(int i = 0; i < N; ++i){
    if(C[i] >= 0) continue;
    C[i] = 0;
    if(G[i].empty()) ++y;
    else ++z, x += dfs(G,i,C);
  }
  long long ans = N*N - (N-y)*(N-y) + z*z + x*x;
  cout << ans << endl;
}

Submission Info

Submission Time
Task C - Squared Graph
User TAB
Language C++14 (GCC 5.4.1)
Score 800
Code Size 806 Byte
Status
Exec Time 161 ms
Memory 11776 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample1.txt, sample2.txt
All 800 / 800 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 1 ms 256 KB
in10.txt 3 ms 2944 KB
in11.txt 1 ms 256 KB
in12.txt 39 ms 6016 KB
in13.txt 38 ms 6144 KB
in14.txt 79 ms 6144 KB
in15.txt 9 ms 3328 KB
in16.txt 57 ms 4608 KB
in17.txt 45 ms 5888 KB
in18.txt 101 ms 7680 KB
in19.txt 81 ms 7808 KB
in2.txt 1 ms 256 KB
in20.txt 81 ms 7936 KB
in21.txt 161 ms 11776 KB
in22.txt 111 ms 4096 KB
in23.txt 89 ms 2560 KB
in24.txt 3 ms 3072 KB
in25.txt 156 ms 11776 KB
in26.txt 1 ms 256 KB
in27.txt 2 ms 256 KB
in28.txt 155 ms 11776 KB
in3.txt 1 ms 256 KB
in4.txt 1 ms 256 KB
in5.txt 114 ms 5632 KB
in6.txt 6 ms 3328 KB
in7.txt 7 ms 3200 KB
in8.txt 15 ms 3840 KB
in9.txt 46 ms 5376 KB
sample1.txt 1 ms 256 KB
sample2.txt 1 ms 256 KB