dwangoプログラミングコンテスト

Submission #596424

Source codeソースコード

#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

Task問題 C - ドライブ
User nameユーザ名 semiexp
Created time投稿日時
Language言語 C++11 (GCC 4.8.1)
Status状態 AC
Score得点 110
Source lengthソースコード長 1197 Byte
File nameファイル名
Exec time実行時間 610 ms
Memory usageメモリ使用量 45440 KB

Compiler messageコンパイルメッセージ

./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);
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt
Subtask1 40 / 40 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 70 / 70 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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