| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 94546 |
2019-01-20T10:49:48 Z |
tpoppo |
Usmjeri (COCI17_usmjeri) |
C++14 |
|
142 ms |
41056 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 10;
const int64_t MOD = 1000000007;
vector<int> grafo[MAXN];
int h[MAXN];
int parent[MAXN];
int in[MAXN];
int out[MAXN];
int dsu[MAXN];
int a,b;
int n,m;
int fast_read_int() {
int c, n = 0;
do c = getchar_unlocked();
while (c < '0' || c > '9' );
do {
n = (n << 3) + (n << 1) + (c - '0');
c = getchar_unlocked();
} while (c >= '0' && c <= '9');
return n;
}
inline int find(int x){
return dsu[x] = dsu[x] == x? x : find(dsu[x]);
}
inline void merge(int x,int y){
x = find(x);
y = find(y);
if(x == y) return ;
if(h[x] > h[y]) swap(x,y);
dsu[y] = x;
}
int cnt;
inline void get_h(int id,int prec,int k=0){
h[id] = k;
in[id] = cnt++;
parent[id] = prec;
for(auto el : grafo[id]){
if(el != prec){
get_h(el,id,k+1);
}
}
out[id] = cnt++;
}
inline bool is_ancestor(int a,int b){
return in[a] <= in[b] && out[b] <= out[a];
}
int main() {
n = fast_read_int();
m = fast_read_int();
for(int i=0;i<n-1;i++){
a = fast_read_int();
b = fast_read_int();
a--;
b--;
grafo[a].push_back(b);
grafo[b].push_back(a);
}
get_h(0,-1);
//for(int i=0;i<n;i++) cout<<i<<": "<<h[i]<<endl;
for(int i=0;i<n;i++) dsu[i] = i;
for(int i=0;i<m;i++){
a = fast_read_int();
b = fast_read_int();
a--;b--;
if(find(a) == find(b)) continue;
//cout<<a<<" "<<b<<endl;
if(is_ancestor(a,b) || is_ancestor(b,a)){
int ra = a;
int rb = b;
a = find(a);
b = find(b);
while(a != b){
if(h[a] < h[b]) swap(a,b);
if(parent[a] == rb || parent[a] == ra) break;
merge(a,parent[a]);
a = find(a);
}
}else{
a = find(a);
b = find(b);
while(parent[b] != parent[a] && a != b){
if(h[a] < h[b]) swap(a,b);
merge(a,parent[a]);
a = find(a);
}
merge(a,b);
}
}
//for(int i=0;i<dsu.size();i++) cout<<i<<": "<<find(i)<<'\n';
int rs = 1;
for(int i=1;i<n;i++){
if(i == find(i)){
rs*=2,rs%=MOD;
}
}
printf("%d",rs);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
19576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
41056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7416 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
7544 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7548 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
7544 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7800 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
7672 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7800 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
7672 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
30712 KB |
Output is correct |
| 2 |
Correct |
133 ms |
30928 KB |
Output is correct |
| 3 |
Incorrect |
69 ms |
21496 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
142 ms |
30736 KB |
Output is correct |
| 2 |
Correct |
134 ms |
30804 KB |
Output is correct |
| 3 |
Incorrect |
102 ms |
22876 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
30856 KB |
Output is correct |
| 2 |
Correct |
123 ms |
30888 KB |
Output is correct |
| 3 |
Incorrect |
76 ms |
22800 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
31096 KB |
Output is correct |
| 2 |
Correct |
113 ms |
31184 KB |
Output is correct |
| 3 |
Incorrect |
106 ms |
21544 KB |
Output isn't correct |
