oj.uz

Submission #1026026

# Submission time Handle Problem Language Result Execution time Memory
1026026 2024-07-17T12:50:00 Z vjudge1 Usmjeri (COCI17_usmjeri) C++17
56 / 140
 7 ms 1884 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1116 KB Output is correct
2 Correct 4 ms 1116 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 3 ms 1116 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1884 KB Output is correct
2 Correct 4 ms 1440 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1884 KB Output is correct
2 Correct 4 ms 1372 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -