Submission #890071

#	Time	Username	Problem	Language	Result	Execution time	Memory
890071		aidfnbvosdnvla	Usmjeri (COCI17_usmjeri)	C++17	126 / 140	330 ms	65208 KiB

usmjeri

#define _USE_MATH_DEFINES

#include <immintrin.h>
#include <math.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <chrono>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

namespace std {

template<typename Fun>
struct y_combinator {
    const Fun fun;

    explicit y_combinator(const Fun&& fun) : fun(std::forward<const Fun>(fun)) {}

    template<typename... Args>
    auto operator()(Args&&... args) const {
        return fun(std::ref(*this), std::forward<Args>(args)...);
    }
};

template <typename T> void mineq(T& element, const T value) {
    element = std::min<T>(element, value);
}

template <typename T> void maxeq(T& element, const T value) {
    element = std::max<T>(element, value);
}

} // namespace std

#define INF ((int)1e9 + 1329)
#define INF_LL ((int64_t)1e18)
#define filin(x) freopen(x, "r", stdin)
#define filout(x) freopen(x, "w", stdout)

typedef int64_t ll;
typedef uint64_t ul;
typedef long double ld;

//const ld PI = acos(-1.0);

#ifndef __APPLE__
mt19937 rnd((uint32_t)time(0));
#else
mt19937 rnd(57);
#endif

struct Solution {
    signed operator()() {
        int n, m; cin >> n >> m;
        vector<vector<pair<int, int>>> g(n);
        for (int i = 0; i < n - 1; ++i) {
            int a, b; cin >> a >> b;
            a--; b--;
            g[a].emplace_back(b, i);
            g[b].emplace_back(a, i);
        }
        constexpr int lg = 22;
        vector<int> pae(n, -1), hst(n - 1);
        array<vector<int>, lg> bp;
        vector<int> dep(n);
        bp.fill(vector<int>(n, -1));
        auto dfs = y_combinator([&](auto dfs, int v = 0, int p = -1, int d = 0, int pe = -1) -> void {
            if (pe != -1)
                hst[pe] = p;
            pae[v] = pe;
            dep[v] = d;
            bp[0][v] = p;
            for (auto& it : g[v])
                if (it.first != p)
                    dfs(it.first, v, d + 1, it.second);
        });
        dfs();
        for (int l = 1; l < lg; ++l)
            for (int i = 0; i < n; ++i)
                bp[l][i] = (bp[l - 1][i] == -1 ? -1 : bp[l - 1][bp[l - 1][i]]);
        auto la = [&](int v, int d) -> int {
            for (int l = 0; l < lg; ++l)
                if ((d >> l) & 1)
                    v = bp[l][v];
            return v;
        };
        auto lca = [&](int a, int b) -> int {
            if (dep[a] < dep[b])
                swap(a, b);
            a = la(a, dep[a] - dep[b]);
            if (a == b)
                return a;
            for (int l = lg - 1; l >= 0; --l) {
                if (bp[l][a] != bp[l][b]) {
                    a = bp[l][a];
                    b = bp[l][b];
                }
            }
            return bp[0][a];
        };
        struct DSU {
            vector<int> dt, sz;
            vector<int> &mx, &dep;
            int comp;
            
            DSU(int n, vector<int>& mx, vector<int>& dep) : mx(mx), dep(dep) {
                int ps = (int)mx.size();
                for (int i = 0; i < ps; ++i)
                    mx.push_back(mx[i]);
                comp = n;
                dt.resize(n);
                iota(dt.begin(), dt.end(), 0);
                sz.resize(n, 1);
            }
            
            int get(int v) {
                return (dt[v] == v ? v : dt[v] = get(dt[v]));
            }
            
            void unite(int a, int b) {
                a = get(a);
                b = get(b);
                if (a == b)
                    return;
                comp--;
                if (sz[a] < sz[b])
                    swap(a, b);
                dt[b] = a;
                sz[a] += sz[b];
                mx[a] = (dep[mx[a]] < dep[mx[b]] ? mx[a] : mx[b]);
            }
        } d((n - 1) * 2, hst, dep);
        auto neg = [&](int v) -> int {
            if (v >= n - 1)
                return v - (n - 1);
            return v + (n - 1);
        };
        while (m--) {
            int a, b; cin >> a >> b;
            a--; b--;
            int lc = lca(a, b);
            int tgd = dep[lc];
            int ora = a, orb = b;
            int v = pae[a];
            if (a != 0)
                a = hst[pae[a]];
            while (a > 0 && dep[a] > tgd) {
                d.unite(v, pae[a]);
                d.unite(neg(v), neg(pae[a]));
                a = d.mx[d.get(v)];
            }
            v = pae[b];
            if (b != 0)
                b = hst[pae[b]];
            while (b > 0 && dep[b] > tgd) {
                d.unite(v, pae[b]);
                d.unite(neg(v), neg(pae[b]));
                b = d.mx[d.get(v)];
            }
            a = ora;
            b = orb;
            if (tgd != dep[a] && tgd != dep[b]) {
                d.unite(pae[a], neg(pae[b]));
                d.unite(neg(pae[a]), pae[b]);
            }
//            for (auto& it : d.dt)
//                cout << it << " ";
//            cout << "\n";
        }
        for (int i = 0; i < n - 1; ++i) {
            if (d.get(i) == d.get(neg(i))) {
                cout << "0\n";
                return 0;
            }
        }
        ll res = 1ll;
        constexpr ll mod = 1e9 + 7;
        assert(d.comp % 2 == 0);
        d.comp /= 2;
        while (d.comp--) {
            res *= 2;
            res %= mod;
        }
        cout << res << "\n";
        return 0;
    }

    Solution() {}
};


signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
//    cin >> t;
    while (t--) {
        int exit_code = Solution()();
        if (exit_code)
            exit(exit_code);
        //        cout << "\n";
    }
    return 0;
}


//3 1
//1 2
//1 3
//2 3

//4 1
//1 2
//2 3
//3 4
//2 4
//
//7 2
//1 2
//1 3
//4 2
//2 5
//6 5
//5 7
//1 7
//2 6
//
//4 3
//1 2
//1 3
//1 4
//2 3
//2 4
//3 4


//WA test 1. Contents:
//6 2
//1 2
//2 3
//3 4
//4 5
//5 6
//5 4
//2 1
//
//Correct:
//32
//Clever:
//16

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 0 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14