oj.uz

Submission #116833

# Submission time Handle Problem Language Result Execution time Memory
116833 2019-06-14T02:10:06 Z josefu_ Usmjeri (COCI17_usmjeri) C++14
28 / 140
 1022 ms 69292 KB 
#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];

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);
	}
}

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)
	{
		par[u] = tmp;
		size[tmp] += size[u];
		u = partree[0][u];
	}
	while(fin(v) != tmp)
	{
		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

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:135: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:140: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:149: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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 27256 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 69292 KB Output is correct

Subtask #3
0 / 14.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 14.0

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

Subtask #6
0 / 14.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 55664 KB Output is correct
2 Correct 705 ms 53496 KB Output is correct
3 Incorrect 375 ms 42492 KB Output isn't correct

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 983 ms 63856 KB Output is correct
2 Correct 724 ms 62200 KB Output is correct
3 Incorrect 642 ms 44152 KB Output isn't correct

Subtask #10
0 / 14.0

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