| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 94547 |
2019-01-20T10:55:06 Z |
tpoppo |
Usmjeri (COCI17_usmjeri) |
C++14 |
|
215 ms |
40376 KB |
#include <bits/stdc++.h>
using namespace std;
const int64_t MAXN = 3e5 + 10;
const int64_t MOD = 1000000007;
vector<int64_t> grafo[MAXN];
int64_t h[MAXN];
int64_t parent[MAXN];
int64_t in[MAXN];
int64_t out[MAXN];
int64_t dsu[MAXN];
int64_t a,b;
int64_t n,m;
int64_t fast_read_int64_t() {
int64_t 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 int64_t find(int64_t x){
return dsu[x] = dsu[x] == x? x : find(dsu[x]);
}
inline void merge(int64_t x,int64_t y){
x = find(x);
y = find(y);
if(x == y) return ;
if(h[x] > h[y]) swap(x,y);
dsu[y] = x;
}
int64_t cnt;
inline void get_h(int64_t id,int64_t prec,int64_t 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(int64_t a,int64_t b){
return in[a] <= in[b] && out[b] <= out[a];
}
int main() {
n = fast_read_int64_t();
m = fast_read_int64_t();
for(int64_t i=0;i<n-1;i++){
a = fast_read_int64_t();
b = fast_read_int64_t();
a--;
b--;
grafo[a].push_back(b);
grafo[b].push_back(a);
}
get_h(0,-1);
//for(int64_t i=0;i<n;i++) cout<<i<<": "<<h[i]<<endl;
for(int64_t i=0;i<n;i++) dsu[i] = i;
for(int64_t i=0;i<m;i++){
a = fast_read_int64_t();
b = fast_read_int64_t();
a--;b--;
if(find(a) == find(b)) continue;
//cout<<a<<" "<<b<<endl;
if(is_ancestor(a,b) || is_ancestor(b,a)){
int64_t ra = a;
int64_t 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(int64_t i=0;i<dsu.size();i++) cout<<i<<": "<<find(i)<<'\n';
int64_t rs = 1;
for(int64_t i=1;i<n;i++){
if(i == find(i)){
rs*=2,rs%=MOD;
}
}
printf("%lld",rs);
return 0;
}
Compilation message
usmjeri.cpp: In function 'int main()':
usmjeri.cpp:113:21: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int64_t {aka long int}' [-Wformat=]
printf("%lld",rs);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
20112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
40376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7544 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
7544 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7416 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
7544 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7928 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
7800 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7800 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
7800 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
127 ms |
31708 KB |
Output is correct |
| 2 |
Correct |
215 ms |
31648 KB |
Output is correct |
| 3 |
Incorrect |
87 ms |
24824 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
31692 KB |
Output is correct |
| 2 |
Correct |
132 ms |
31736 KB |
Output is correct |
| 3 |
Incorrect |
119 ms |
24472 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
165 ms |
31892 KB |
Output is correct |
| 2 |
Correct |
186 ms |
31736 KB |
Output is correct |
| 3 |
Incorrect |
124 ms |
24348 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
179 ms |
31920 KB |
Output is correct |
| 2 |
Correct |
149 ms |
31940 KB |
Output is correct |
| 3 |
Incorrect |
123 ms |
24592 KB |
Output isn't correct |
