oj.uz

답안 #94546

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94546 2019-01-20T10:49:48 Z tpoppo Usmjeri (COCI17_usmjeri) C++14
28 / 140
 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;
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 19576 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 41056 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Incorrect 8 ms 7544 KB Output isn't correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7548 KB Output is correct
2 Incorrect 8 ms 7544 KB Output isn't correct

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7800 KB Output is correct
2 Incorrect 8 ms 7672 KB Output isn't correct

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7800 KB Output is correct
2 Incorrect 9 ms 7672 KB Output isn't correct

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 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

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 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

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 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

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 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