Submission #3402626


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 + 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 + 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 2413 Byte
Status WA
Exec Time 338 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 2 ms 384 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 170 ms 6144 KB
in15.txt WA 15 ms 3328 KB
in16.txt WA 127 ms 4608 KB
in17.txt WA 94 ms 5376 KB
in18.txt WA 231 ms 6144 KB
in19.txt WA 173 ms 5760 KB
in2.txt WA 1 ms 256 KB
in20.txt WA 175 ms 5760 KB
in21.txt WA 333 ms 7168 KB
in22.txt WA 282 ms 3328 KB
in23.txt WA 239 ms 2432 KB
in24.txt WA 4 ms 3072 KB
in25.txt WA 338 ms 7168 KB
in26.txt WA 1 ms 256 KB
in27.txt WA 3 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 272 ms 5760 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 101 ms 4352 KB
sample1.txt AC 1 ms 256 KB
sample2.txt AC 1 ms 256 KB