Submission #1370478


Source Code Expand

/*
 _    _    _______   _    _
| |  / /  |  _____| | |  / /
| | / /   | |       | | / /
| |/ /    | |_____  | |/ /
| |\ \    |  _____| | |\ \
| | \ \   | |       | | \ \
| |  \ \  | |_____  | |  \ \
|_|   \_\ |_______| |_|   \_\

*/
/*#include <iostream>
#include <cstdio>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <cstring>
#include <string>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <assert.h>*/

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;

#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define right(x) x << 1 | 1
#define left(x) x << 1
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define mkp make_pair
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define y1 kekekek

const ll ool = 1e18 + 9;
const int oo = 1e9 + 9, base = 1e9 + 7;
const ld eps = 1e-7;
const int N = 2e6 + 6;

int n, m, cnt, sz[N], col[N];
bool u[N], bad[N];
vector < int > g[N];

void dfs(int v) {
    u[v] = 1;
    sz[cnt]++;
    for (auto to : g[v]) {
        if (u[to] && col[to] == col[v]) bad[cnt] = 1;
        if (u[to]) continue;
        col[to] = col[v] ^ 1;
        dfs(to);
    }
}

int main() {
	ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> n >> m;
    forn(i, 1, m) {
        int x, y;
        cin >> x >> y;
        g[x].eb(y);
        g[y].eb(x);
    }

    forn(i, 1, n) {
        if (!u[i]) {
            ++cnt;
            dfs(i);
        }
    }

    ll ans = 1ll * n * n, sum = 0, c = 0;

    forn(i, 1, cnt) {
        if (sz[i] == 1) continue;
        ans -= sz[i] * sum * 2 + 1ll * sz[i] * sz[i];
        sum += sz[i];
        //cerr << ans << "\n";
        //cerr << bad[i] << "\n";
        if (bad[i]) {
            ans += 2 * (i - 1) + 1;
        }
        else {
            //cerr << ans << "\n";
            ans += (i - c - 1) * 2 + 1ll * c * 4 + 2;
            ++c;
        }
    }

    cout << ans << "\n";

	return 0;
}

Submission Info

Submission Time
Task C - Squared Graph
User krauch
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2268 Byte
Status WA
Exec Time 93 ms
Memory 59520 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 800
Status
AC × 2
AC × 11
WA × 21
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 18 ms 53504 KB
in10.txt AC 18 ms 51456 KB
in11.txt WA 18 ms 53504 KB
in12.txt WA 37 ms 56704 KB
in13.txt AC 37 ms 56576 KB
in14.txt AC 54 ms 56576 KB
in15.txt WA 22 ms 53888 KB
in16.txt WA 45 ms 55040 KB
in17.txt WA 40 ms 56064 KB
in18.txt WA 68 ms 57216 KB
in19.txt WA 56 ms 57088 KB
in2.txt WA 18 ms 53504 KB
in20.txt WA 57 ms 57088 KB
in21.txt WA 91 ms 59520 KB
in22.txt AC 63 ms 56704 KB
in23.txt AC 50 ms 55680 KB
in24.txt WA 19 ms 53504 KB
in25.txt WA 92 ms 59520 KB
in26.txt WA 18 ms 53504 KB
in27.txt WA 18 ms 53504 KB
in28.txt WA 93 ms 59520 KB
in3.txt AC 18 ms 53504 KB
in4.txt AC 18 ms 53504 KB
in5.txt WA 66 ms 56192 KB
in6.txt WA 21 ms 53760 KB
in7.txt WA 20 ms 53632 KB
in8.txt WA 25 ms 54400 KB
in9.txt WA 39 ms 55296 KB
sample1.txt AC 18 ms 53504 KB
sample2.txt AC 18 ms 53504 KB