Submission #3402809


Source Code Expand

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//ここから編集する

int N, M;
vector<vector<int> > G;

vector<int> color;

// ぼっちなら0
// 二部グラフなら1
// 二部グラフじゃないなら-1
// paint(v,1)で呼び出す
int paint(int v, int c) {
    if (G[v].size() == 0) return 0;
    if (color[v] != 0) {
        if (color[v] != c) return -1;
        return 1;
    }

    color[v] = c;

    for (auto e : G[v]) {
        if (paint(e, -c) == -1) {
            return -1;
        }
    }

    return 1;


}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N >> M;
    G.resize(N);
    color.resize(N);


    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    // x 二部じゃない y 二部 z ぼっち
    //(x + y) ^ 2 + y * y + 2 * z * N - 1が答え
    ll x = 0ll, y = 0ll, z = 0ll;

    for(int i = 0; i < N; ++i){
        if(color[i] == 0){
            int val = paint(i,1);
            if(val == 0) z++;
            if(val == 1) y++;
            if(val == -1) x++;
        }
    }

    ll ans = (x + y) * (x + y) + y * y + 2 * z * N - 1;
    cout << ans << endl;

    return 0;
}

Submission Info

Submission Time
Task C - Squared Graph
User homesentinel
Language C++14 (Clang 3.8.0)
Score 0
Code Size 2421 Byte
Status WA
Exec Time 335 ms
Memory 7168 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 800
Status
AC × 2
AC × 4
WA × 28
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 WA 1 ms 256 KB
in10.txt WA 3 ms 2944 KB
in11.txt WA 1 ms 256 KB
in12.txt WA 87 ms 6144 KB
in13.txt WA 88 ms 6144 KB
in14.txt WA 171 ms 6144 KB
in15.txt WA 16 ms 3328 KB
in16.txt WA 128 ms 4608 KB
in17.txt WA 95 ms 5376 KB
in18.txt WA 233 ms 6144 KB
in19.txt WA 172 ms 5760 KB
in2.txt WA 1 ms 256 KB
in20.txt WA 173 ms 5760 KB
in21.txt WA 334 ms 7168 KB
in22.txt WA 280 ms 3328 KB
in23.txt WA 238 ms 2432 KB
in24.txt WA 3 ms 3072 KB
in25.txt WA 331 ms 7168 KB
in26.txt WA 1 ms 256 KB
in27.txt WA 2 ms 256 KB
in28.txt WA 335 ms 7168 KB
in3.txt WA 1 ms 256 KB
in4.txt WA 1 ms 256 KB
in5.txt WA 271 ms 5632 KB
in6.txt WA 12 ms 3328 KB
in7.txt WA 14 ms 3072 KB
in8.txt WA 31 ms 3840 KB
in9.txt WA 102 ms 4352 KB
sample1.txt AC 1 ms 256 KB
sample2.txt AC 1 ms 256 KB