Submission #353883


Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <climits>
using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define RREP(i,n) for(int i=(int)n-1; i>=0; i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();++i)
#define ALL(c) (c).begin(), (c).end()

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > pipii;
typedef vector<int> vi;

const int INF = 1e9;
const int MOD = 1e9+7;


struct UnionFind {
    vector<int> data;
    UnionFind(int size) : data(size, -1) { }
    bool unionSet(int x, int y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
        return x != y;
    }
    bool findSet(int x, int y) {
        return root(x) == root(y);
    }
    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
};

int main(void){
    int N, M;
    cin >> N >> M;
    if(N > 2525 || M > 2525) return 0;
    vector<pii> e;
    vector<ll> cost(M, 2);
    for(int i = 1; i < M; i++) (cost[i] = cost[i-1] * 2) %= MOD;
    ll ans = 0LL;
    vi even(N, 0);
    REP(i, M){
        int a, b;
        cin >> a >> b;
        a--; b--;
        e.push_back(make_pair(a, b));
        even[a]++; even[b]++;
        ans = (ans + cost[i]) % MOD;
    }
    REP(i, N) even[i] %= 2;
    vector<pii> use;
    RREP(i, e.size()){
        int x = e[i].first, y = e[i].second;

        UnionFind uf(N);
        FOR(u, use){
            int a = (*u).first, b = (*u).second;
            uf.unionSet(a, b);
        }
        REP(j, i){
            int a = e[j].first, b = e[j].second;
            uf.unionSet(a, b);
        }

        vi evennum(N, 0);
        REP(j, N){
            if(even[j]){
                evennum[uf.root(j)]++;
            }
        }
        int f = 0;
        REP(j, N){
            if((evennum[j] % 2)) f = 1;
        }
        if(f){
            use.push_back(e[i]);
            ans = (ans + cost[i]) % MOD;
            (even[e[i].first] += 1) %= 2;
            (even[e[i].second] += 1) %= 2;
        }
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task C - ドライブ
User no15_renne
Language C++ (G++ 4.6.4)
Score 40
Code Size 2545 Byte
Status WA
Exec Time 288 ms
Memory 1260 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 40 / 40 0 / 70
Status
AC × 2
AC × 20
AC × 18
WA × 15
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
Subtask1 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt
Subtask2 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt
Case Name Status Exec Time Memory
sample_01.txt AC 35 ms 1100 KB
sample_02.txt AC 34 ms 1132 KB
subtask1_01.txt AC 34 ms 1124 KB
subtask1_02.txt AC 32 ms 1132 KB
subtask1_03.txt AC 32 ms 1044 KB
subtask1_04.txt AC 288 ms 1180 KB
subtask1_05.txt AC 207 ms 1176 KB
subtask1_06.txt AC 212 ms 1176 KB
subtask1_07.txt AC 190 ms 1188 KB
subtask1_08.txt AC 178 ms 1128 KB
subtask1_09.txt AC 241 ms 1176 KB
subtask1_10.txt AC 285 ms 1176 KB
subtask1_11.txt AC 287 ms 1256 KB
subtask1_12.txt AC 219 ms 1176 KB
subtask1_13.txt AC 267 ms 1180 KB
subtask1_14.txt AC 145 ms 1172 KB
subtask1_15.txt AC 70 ms 1196 KB
subtask1_16.txt AC 208 ms 1260 KB
subtask1_17.txt AC 138 ms 1124 KB
subtask1_18.txt AC 78 ms 1136 KB
subtask2_01.txt WA 50 ms 1128 KB
subtask2_02.txt WA 49 ms 1136 KB
subtask2_03.txt WA 48 ms 1128 KB
subtask2_04.txt WA 43 ms 1128 KB
subtask2_05.txt WA 42 ms 1124 KB
subtask2_06.txt WA 41 ms 1128 KB
subtask2_07.txt WA 46 ms 1132 KB
subtask2_08.txt WA 44 ms 1128 KB
subtask2_09.txt WA 44 ms 1128 KB
subtask2_10.txt WA 32 ms 1124 KB
subtask2_11.txt WA 31 ms 1124 KB
subtask2_12.txt WA 45 ms 1128 KB
subtask2_13.txt WA 41 ms 1128 KB
subtask2_14.txt WA 34 ms 1128 KB
subtask2_15.txt WA 33 ms 1048 KB