Submission #1026026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026026		vjudge1	Usmjeri (COCI17_usmjeri)	C++17	56 / 140	7 ms	1884 KiB

usmjeri

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 1e9 + 7;

int power(int a,int b)
{
	int ans=1;
	while (b)
	{
		if (b&1)
			ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;	
	}
	return ans;
}

const int M = 5001;

vector<int> nei[M],prs[M],fir[M],sec[M];
unordered_map<int,int> ind;
int dep[M],par[M],dir[M],ans=1;
bool vis[M];

int val(int u,int v)
{
	return min(u,v)*(M-1)+u+v;
}

void dfs(int u)
{
	for (int i:nei[u])
		if (i!=par[u])
		{
			par[i]=u;
			dep[i]=dep[u]+1;
			dfs(i);
		}
}

void lca(int u,int v,int i)
{
	while (dep[u]>dep[v])
	{
		int x=val(u,par[u]);
		fir[i].push_back(ind[x]);
		prs[ind[x]].push_back(i);
		u=par[u];
	}
	while (dep[v]>dep[u])
	{
		int x=val(v,par[v]);
		sec[i].push_back(ind[x]);
		prs[ind[x]].push_back(-i);
		v=par[v];
	}
	while (u!=v)
	{
		int x=val(u,par[u]);
		fir[i].push_back(ind[x]);
		prs[ind[x]].push_back(i);
		u=par[u];
		x=val(v,par[v]);
		sec[i].push_back(ind[x]);
		prs[ind[x]].push_back(-i);
		v=par[v];
	}
}

void make_path(int id,int dr)
{
	if (vis[id])
		return;
	vis[id]=1;
	for (int i:fir[id])
	{
		if (dir[i] && dir[i]!=dr)
			ans=0;
		dir[i]=dr;
	}
	for (int i:sec[id])
	{
		if (dir[i] && dir[i]!=3-dr)
			ans=0;
		dir[i]=3-dr;
	}
	for (int i:fir[id])
		for (int j:prs[i])
		{
			if (j>0)
				make_path(j,dr);
			else
				make_path(-j,3-dr);
		}
	for (int i:sec[id])
		for (int j:prs[i])
		{
			if (j>0)
				make_path(j,3-dr);
			else
				make_path(-j,dr);	
		}	
}

signed main()
{
	int n,m;
	cin>>n>>m;
	if (n<=5000)
	{
		for (int i=1;i<n;i++)
		{
			int u,v;
			cin>>u>>v;
			nei[u].push_back(v);
			nei[v].push_back(u);
			ind[val(u,v)]=i;
		}
		dfs(1);
		int a[m+1],b[m+1];
		for (int i=1;i<=m;i++)
		{
			cin>>a[i]>>b[i];
			lca(a[i],b[i],i);
		}
		for (int i=1;i<=m;i++)
		{
			if (!vis[i])
			{
				make_path(i,1);
				ans=ans*2%mod;
			}
		}
		for (int i=1;i<n;i++)
			if (!dir[i])
				ans=ans*2%mod;
		cout<<ans<<endl;
	}
	
	return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14