Submission #353878
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;
vector<pii> e;
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 + (1 << (i+1))) % 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 + (1<<(i+1))) % 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 |
0 |
Code Size |
2419 Byte |
Status |
WA |
Exec Time |
2062 ms |
Memory |
9772 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
0 / 40 |
0 / 70 |
Status |
|
|
|
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 |
47 ms |
1208 KB |
sample_02.txt |
AC |
37 ms |
1204 KB |
subtask1_01.txt |
AC |
34 ms |
1212 KB |
subtask1_02.txt |
AC |
34 ms |
1300 KB |
subtask1_03.txt |
AC |
35 ms |
1204 KB |
subtask1_04.txt |
WA |
286 ms |
1208 KB |
subtask1_05.txt |
WA |
212 ms |
1208 KB |
subtask1_06.txt |
WA |
216 ms |
1200 KB |
subtask1_07.txt |
WA |
195 ms |
1276 KB |
subtask1_08.txt |
WA |
180 ms |
1204 KB |
subtask1_09.txt |
WA |
239 ms |
1168 KB |
subtask1_10.txt |
WA |
283 ms |
1344 KB |
subtask1_11.txt |
WA |
286 ms |
1200 KB |
subtask1_12.txt |
WA |
218 ms |
1216 KB |
subtask1_13.txt |
WA |
268 ms |
1296 KB |
subtask1_14.txt |
WA |
147 ms |
1288 KB |
subtask1_15.txt |
WA |
69 ms |
1212 KB |
subtask1_16.txt |
WA |
205 ms |
1296 KB |
subtask1_17.txt |
WA |
144 ms |
1208 KB |
subtask1_18.txt |
WA |
277 ms |
1216 KB |
subtask2_01.txt |
TLE |
2054 ms |
9768 KB |
subtask2_02.txt |
TLE |
2052 ms |
9768 KB |
subtask2_03.txt |
TLE |
2051 ms |
9772 KB |
subtask2_04.txt |
TLE |
2062 ms |
9764 KB |
subtask2_05.txt |
TLE |
2044 ms |
9100 KB |
subtask2_06.txt |
TLE |
2043 ms |
9068 KB |
subtask2_07.txt |
TLE |
2048 ms |
8916 KB |
subtask2_08.txt |
TLE |
2037 ms |
8960 KB |
subtask2_09.txt |
TLE |
2054 ms |
9680 KB |
subtask2_10.txt |
TLE |
2038 ms |
3036 KB |
subtask2_11.txt |
TLE |
2036 ms |
5396 KB |
subtask2_12.txt |
TLE |
2056 ms |
7636 KB |
subtask2_13.txt |
TLE |
2047 ms |
8400 KB |
subtask2_14.txt |
TLE |
2049 ms |
9044 KB |
subtask2_15.txt |
TLE |
2037 ms |
5336 KB |