Submission #94546

#	Time	Username	Problem	Language	Result	Execution time	Memory
94546		tpoppo	Usmjeri (COCI17_usmjeri)	C++14	28 / 140	142 ms	41056 KiB

usmjeri

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14