Submission #94547

#	Time	Username	Problem	Language	Result	Execution time	Memory
94547		tpoppo	Usmjeri (COCI17_usmjeri)	C++14	28 / 140	215 ms	40376 KiB

usmjeri

#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 (stderr)

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);
                     ^

• 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