Submission #338133


Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <set>
#define SIZE 400005
#define MOD 1000000007

using namespace std;

struct edge
{
	int to,id;
	edge(int to=0,int id=0):to(to),id(id){}
};
struct UF
{
	int par[SIZE],rank[SIZE];
	
	void init(int n)
	{
		for(int i=0;i<n;i++)
		{
			par[i]=i;
			rank[i]=0;
		}
	}
	int find(int x)
	{
		if(par[x]==x) return x;
		return par[x]=find(par[x]);
	}
	void unite(int x,int y)
	{
		x=find(x);
		y=find(y);
		if(x==y) return;
		if(rank[x]<rank[y])
		{
			par[x]=y;
		}
		else
		{
			par[y]=x;
			if(rank[x]==rank[y]) rank[x]++;
		}
	}
	bool same(int x,int y)
	{
		return find(x)==find(y);
	}
};
UF uf;
vector <edge> vec[SIZE];
int cnt[SIZE];

int dfs(int v,int p)
{
	int ret=0;
	for(int i=0;i<vec[v].size();i++)
	{
		edge e=vec[v][i];
		if(e.to!=p)
		{
			ret+=dfs(e.to,v);
			ret%=MOD;
			cnt[v]^=cnt[e.to];
			if(cnt[e.to]==0)
			{
				ret+=e.id;
				ret%=MOD;
			}
		}
	}
	return ret;
}
int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	uf.init(n+2);
	int rt=1,ret=0;
	for(int i=0;i<m;i++)
	{
		rt<<=1;
		rt%=MOD;
		int a,b;
		scanf("%d %d",&a,&b);a--;b--;
		if(uf.same(a,b))
		{
			cnt[a]^=1;
			cnt[b]^=1;
		}
		else
		{
			uf.unite(a,b);
			vec[a].push_back(edge(b,rt));
			vec[b].push_back(edge(a,rt));
		}
		ret+=rt;
		ret%=MOD;
	}
	printf("%d\n",(ret+dfs(0,-1))%MOD);
	return 0;
}

Submission Info

Submission Time
Task C - ドライブ
User yutaka1999
Language C++ (G++ 4.6.4)
Score 110
Code Size 1529 Byte
Status AC
Exec Time 698 ms
Memory 43944 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:83:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:91:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

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 45 ms 10152 KB
sample_02.txt AC 43 ms 10152 KB
subtask1_01.txt AC 39 ms 10140 KB
subtask1_02.txt AC 41 ms 10264 KB
subtask1_03.txt AC 42 ms 10092 KB
subtask1_04.txt AC 40 ms 10272 KB
subtask1_05.txt AC 43 ms 10216 KB
subtask1_06.txt AC 42 ms 10276 KB
subtask1_07.txt AC 39 ms 10272 KB
subtask1_08.txt AC 40 ms 10148 KB
subtask1_09.txt AC 41 ms 10280 KB
subtask1_10.txt AC 43 ms 10244 KB
subtask1_11.txt AC 41 ms 10280 KB
subtask1_12.txt AC 42 ms 10280 KB
subtask1_13.txt AC 43 ms 10404 KB
subtask1_14.txt AC 43 ms 10148 KB
subtask1_15.txt AC 39 ms 10144 KB
subtask1_16.txt AC 41 ms 10280 KB
subtask1_17.txt AC 41 ms 10272 KB
subtask1_18.txt AC 40 ms 10152 KB
subtask2_01.txt AC 682 ms 29352 KB
subtask2_02.txt AC 678 ms 29536 KB
subtask2_03.txt AC 490 ms 29964 KB
subtask2_04.txt AC 674 ms 28576 KB
subtask2_05.txt AC 635 ms 29600 KB
subtask2_06.txt AC 639 ms 29728 KB
subtask2_07.txt AC 381 ms 28812 KB
subtask2_08.txt AC 698 ms 43944 KB
subtask2_09.txt AC 653 ms 29732 KB
subtask2_10.txt AC 154 ms 14556 KB
subtask2_11.txt AC 137 ms 10792 KB
subtask2_12.txt AC 421 ms 21276 KB
subtask2_13.txt AC 607 ms 26148 KB
subtask2_14.txt AC 603 ms 28836 KB
subtask2_15.txt AC 163 ms 10148 KB