| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 116832 |
2019-06-14T02:06:14 Z |
josefu_ |
Usmjeri (COCI17_usmjeri) |
C++14 |
|
796 ms |
262144 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], 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
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);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
187 ms |
43816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
415 ms |
102380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
15360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
15360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
755 ms |
77020 KB |
Output is correct |
| 2 |
Correct |
796 ms |
75420 KB |
Output is correct |
| 3 |
Runtime error |
524 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
605 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
610 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
612 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
