Submission #116832

#	Time	Username	Problem	Language	Result	Execution time	Memory
116832		josefu_	Usmjeri (COCI17_usmjeri)	C++14	28 / 140	796 ms	262144 KiB

usmjeri

#define SuC_VaT              Doc_code_ban_khac
#define Nhan_cach_bang_0     Doc_code_ban_khac

//

#include <iostream>
#include <map>
#include <set>
#include <deque>
#include <vector>
#include <list>
#include <string>
#include <math.h>
#include <algorithm>
#include <iomanip>
#include <unordered_map>
#include <queue>
#include <stack>
#include <cstring>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int,int> ii;
typedef pair<ll, pair<ll,ll> > iii;

const int kn = 3e5 + 5, N = 1e5+5;
const ll mod = 1e9 + 7, mod2 = 1e9+9;
const ll base = 31, base1 = 37;

#define x first
#define y second
#define lwb lower_bound
#define upb upper_bound
#define _it iterator

#define pb push_back
#define popb pop_back
#define pf push_front
#define popf pop_front

#define log2(X) (31-__builtin_clz(X))
#define log2ll(X) (63-__builtin_clzll(X))
#define numbit(X) __builtin_popcount(X)
#define numbitll(X) __builtin_popcountll(X)

#define ms(val,a) memset(a,val,sizeof(a))

#define ff(i,n) for(int i=1;i<=n;i++)
#define _ff(i,n) for(int i=n;i>=1;i--)
#define f(i,a,b) for(int i = a; i <=b; i++)
#define _f(i,a,b) for(int i = b; i>=a;i--)

#define In(X) freopen(X,"r",stdin)
#define Out(X) freopen(X,"w",stdout)

#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int n,m, size[kn];
int par[kn], dep[kn];
int partree[19][kn];

set<int> hi;

vector<int> G[kn], child[kn];

void dfs(int u, int v)
{
	dep[u] = dep[v] + 1;
	partree[0][u] = v;
	for(int p : G[u])
	{
		if(p == v) continue;
		dfs(p,u);
		child[u].push_back(p);
	}
}

int fin(int u)
{
	if(par[u] == u) return u;
	return par[u] = fin(par[u]);
}

void build()
{
	ff(k,18)
	{
		ff(i,n)
		{
			partree[k][i] = partree[k-1][partree[k-1][i]];
		}
	}
}

int lca(int u, int v)
{
	if(dep[u] < dep[v]) swap(u,v);
	for(int k = 18; k>=0; k--) if(dep[partree[k][u]] >= dep[v]) u = partree[k][u];
	for(int k = 18; k>=0; k--) if(partree[k][u] != partree[k][v]) u=partree[k][u],v=partree[k][v];
	while(u!=v) u = partree[0][u], v = partree[0][v];
	return u;	
}

void path(int u, int v)
{
	int tmp = lca(u,v);
	tmp = fin(tmp);
	while(fin(u) != tmp)
	{
		for(int p : child[u])
		{
			child[tmp].push_back(p);
		}
		par[u] = tmp;
		size[tmp] += size[u];
		u = partree[0][u];
	}
	while(fin(v) != tmp)
	{
		for(int p : child[v])
		{
			child[tmp].push_back(p);
		}
		par[v] = tmp;
		size[tmp] += size[v];
		v = partree[0][v];
	}
}

ll pow2_(int v)
{
	if(v == 0) return 1;
	if(v == 1) return 2; 
	ll tmp = pow2_(v/2);
	tmp = (tmp*tmp)%mod;
	if(v&1) return (tmp*2)%mod;
	return tmp;
}

int main() {
	scanf("%d%d",&n,&m);
	ff(i,n) par[i] = i, size[i] = 1;
	ff(i,n-1)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,0);
	build();
	while(m--)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		path(u,v);
	}
	//puts("hi");
	ff(i,n)
	{
		//cout << i <<" "<<fin(i) << endl;
		hi.insert(fin(i));
	}
	//cout <<"sz "<< hi.size() << endl;
	ll ans = 1;
	for(int tmp : hi)
	{
		//cout << tmp <<" "<<size[tmp] << endl;
		if(size[tmp]>1) ans*=2;
		if(ans>mod) ans%=mod;
	}
	ans*=pow2_(hi.size()-1);
	cout<<ans%mod;
}
//hahahahahahahahahhahahahahahaahahahahhahahahahahahah

Compilation message (stderr)

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:144:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
usmjeri.cpp:149:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~
usmjeri.cpp:158:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~

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