Submission #338134


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 711 ms
Memory 44048 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 42 ms 10144 KB
sample_02.txt AC 42 ms 10144 KB
subtask1_01.txt AC 39 ms 10144 KB
subtask1_02.txt AC 40 ms 10152 KB
subtask1_03.txt AC 39 ms 10100 KB
subtask1_04.txt AC 42 ms 10276 KB
subtask1_05.txt AC 40 ms 10272 KB
subtask1_06.txt AC 41 ms 10280 KB
subtask1_07.txt AC 39 ms 10276 KB
subtask1_08.txt AC 40 ms 10156 KB
subtask1_09.txt AC 42 ms 10268 KB
subtask1_10.txt AC 41 ms 10284 KB
subtask1_11.txt AC 42 ms 10276 KB
subtask1_12.txt AC 39 ms 10252 KB
subtask1_13.txt AC 42 ms 10352 KB
subtask1_14.txt AC 41 ms 10152 KB
subtask1_15.txt AC 41 ms 10148 KB
subtask1_16.txt AC 41 ms 10276 KB
subtask1_17.txt AC 40 ms 10144 KB
subtask1_18.txt AC 39 ms 10152 KB
subtask2_01.txt AC 693 ms 29300 KB
subtask2_02.txt AC 707 ms 29472 KB
subtask2_03.txt AC 512 ms 29964 KB
subtask2_04.txt AC 696 ms 28656 KB
subtask2_05.txt AC 660 ms 29476 KB
subtask2_06.txt AC 616 ms 29792 KB
subtask2_07.txt AC 381 ms 28828 KB
subtask2_08.txt AC 711 ms 44048 KB
subtask2_09.txt AC 677 ms 29736 KB
subtask2_10.txt AC 164 ms 14496 KB
subtask2_11.txt AC 134 ms 10860 KB
subtask2_12.txt AC 429 ms 21276 KB
subtask2_13.txt AC 638 ms 26148 KB
subtask2_14.txt AC 624 ms 28824 KB
subtask2_15.txt AC 162 ms 10152 KB