Submission #3407481


Source Code Expand

/*input
5 5
1 2
2 3
3 1
5 4
5 1
6 5
1 2
2 3
3 4
4 5
5 6
*/
#include <bits/stdc++.h>
#define db(x) cout<<#x<<"="<<(x)<<" "
#define el cout<<endl
using namespace std;
const int MXN = 1e6 + 10;

int M, N; long long ans;
int fus[MXN], c[MXN], cl[MXN], sz[MXN][4];
int GF(int x) {
    if (x == fus[x])
        return x;
    int r = GF(fus[x]);
    c[x] ^= c[fus[x]];
    return fus[x] = r;
}
int main() {
    cin >> N >> M; // n = N;
    iota(fus, fus + N + 1, 0);
    for (int t = 1; t <= M; ++t) {
        int x, y;
        cin >> x >> y;
        int rx = GF(x), ry = GF(y);
        if (rx == ry) {
            if (c[x] ^ c[y] ^ 1) {

                cl[rx] = 1;
            } else {
            }
        } else {
            fus[rx] = ry;
            cl[ry] |= cl[rx];
            c[rx] = c[x] ^ c[y] ^ 1;
        }
    }
    for (int i = 1; i <= N; ++i)
    {
        int r = GF(i);
        sz[r][c[i]]++;
    }
    for (int i = 1; i <= N; ++i)
    {
        int r = GF(i);
        if (i == r) {
            //db(cl[r]), db(r), db(sz[i][0]), db(sz[i][1]), el;
            if (!cl[r]) {
                ans += sz[i][0] * sz[i][1];
            }
            else {
                int t = sz[i][0] + sz[i][1];
                ans += (t - 1) * t / 2;
            }
        }
    }
    cout  << ans - M << endl;
    return 0;
}

Submission Info

Submission Time
Task C - 3 Steps
User Laurant
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1394 Byte
Status WA
Exec Time 81 ms
Memory 6400 KB

Judge Result

Set Name sample all
Score / Max Score 0 / 0 0 / 500
Status
AC × 2
AC × 19
WA × 9
Set Name Test Cases
sample sample-01.txt, sample-02.txt
all sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
01-01.txt AC 4 ms 6400 KB
01-02.txt AC 3 ms 6400 KB
01-03.txt AC 3 ms 6400 KB
01-04.txt AC 3 ms 6400 KB
01-05.txt AC 3 ms 6400 KB
01-06.txt AC 3 ms 6400 KB
01-07.txt AC 3 ms 6400 KB
01-08.txt AC 3 ms 6400 KB
01-09.txt AC 4 ms 6400 KB
01-10.txt AC 5 ms 6400 KB
02-01.txt WA 80 ms 6400 KB
02-02.txt WA 79 ms 6400 KB
02-03.txt WA 78 ms 6400 KB
02-04.txt WA 79 ms 6400 KB
02-05.txt WA 79 ms 6400 KB
02-06.txt WA 79 ms 6400 KB
02-07.txt WA 77 ms 6400 KB
02-08.txt WA 80 ms 6400 KB
02-09.txt WA 78 ms 6400 KB
02-10.txt AC 54 ms 6400 KB
02-11.txt AC 64 ms 6400 KB
02-12.txt AC 79 ms 6400 KB
02-13.txt AC 81 ms 6400 KB
02-14.txt AC 79 ms 6400 KB
sample-01.txt AC 3 ms 6400 KB
sample-02.txt AC 3 ms 6400 KB