Submission #596424


Source Code Expand

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MOD = 1000000007;
int N, M;
vector<int> A, B, W;
vector<pair<int, int> > graph[400400];

int uf[400400];
int pow2[500500];
int odd[400400];

int root(int p)
{
	return (uf[p] < 0) ? p : (uf[p] = root(uf[p]));
}
bool join(int p, int q)
{
	p = root(p); q = root(q);
	if (p == q) return false;
	uf[p] += uf[q];
	uf[q] = p;
	return true;
}

int ans;
int visit(int p, int rt)
{
	int ret = odd[p];
	for (auto e : graph[p]) if (e.first != rt) {
		int s = visit(e.first, p);
		if (s % 2) ans = (ans + pow2[e.second]) % MOD;
		ret += s;
	}
	return ret;
}
int main()
{
	scanf("%d%d", &N, &M);
	for (int i = 0; i < N; ++i) uf[i] = -1;

	ans = 0;
	pow2[0] = 2;
	for (int i = 0; i < M; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		--x; --y;
		odd[x] ^= 1;
		odd[y] ^= 1;

		if (join(x, y)) {
			A.push_back(x); B.push_back(y); W.push_back(i);
			graph[x].push_back(make_pair(y, i));
			graph[y].push_back(make_pair(x, i));
		}

		if (i) pow2[i] = pow2[i - 1] * 2 % MOD;
		ans = (ans + pow2[i]) % MOD;
	}

	visit(0, -1);
	printf("%d\n", ans);
	return 0;
}

Submission Info

Submission Time
Task C - ドライブ
User semiexp
Language C++11 (GCC 4.8.1)
Score 110
Code Size 1197 Byte
Status AC
Exec Time 610 ms
Memory 45440 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:41:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
./Main.cpp:48:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
                        ^

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 40 / 40 70 / 70
Status
AC × 2
AC × 20
AC × 33
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 72 ms 10216 KB
sample_02.txt AC 61 ms 10216 KB
subtask1_01.txt AC 97 ms 10216 KB
subtask1_02.txt AC 85 ms 10220 KB
subtask1_03.txt AC 66 ms 10224 KB
subtask1_04.txt AC 44 ms 10404 KB
subtask1_05.txt AC 44 ms 10416 KB
subtask1_06.txt AC 43 ms 10412 KB
subtask1_07.txt AC 45 ms 10412 KB
subtask1_08.txt AC 44 ms 10412 KB
subtask1_09.txt AC 45 ms 10416 KB
subtask1_10.txt AC 45 ms 10412 KB
subtask1_11.txt AC 48 ms 10420 KB
subtask1_12.txt AC 42 ms 10404 KB
subtask1_13.txt AC 45 ms 10536 KB
subtask1_14.txt AC 42 ms 10404 KB
subtask1_15.txt AC 44 ms 10276 KB
subtask1_16.txt AC 45 ms 10452 KB
subtask1_17.txt AC 44 ms 10320 KB
subtask1_18.txt AC 42 ms 10272 KB
subtask2_01.txt AC 594 ms 34492 KB
subtask2_02.txt AC 599 ms 34752 KB
subtask2_03.txt AC 480 ms 35220 KB
subtask2_04.txt AC 610 ms 33856 KB
subtask2_05.txt AC 526 ms 34236 KB
subtask2_06.txt AC 516 ms 34548 KB
subtask2_07.txt AC 380 ms 35240 KB
subtask2_08.txt AC 568 ms 45440 KB
subtask2_09.txt AC 559 ms 34880 KB
subtask2_10.txt AC 134 ms 15892 KB
subtask2_11.txt AC 145 ms 12204 KB
subtask2_12.txt AC 397 ms 25156 KB
subtask2_13.txt AC 479 ms 30584 KB
subtask2_14.txt AC 547 ms 33732 KB
subtask2_15.txt AC 214 ms 12264 KB