Submission #890070

#TimeUsernameProblemLanguageResultExecution timeMemory
890070aidfnbvosdnvlaUsmjeri (COCI17_usmjeri)C++14
Compilation error
0 ms0 KiB
#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

Compilation message (stderr)

usmjeri.cpp: In member function 'int Solution::operator()()':
usmjeri.cpp:92:32: error: missing template arguments before '(' token
   92 |         auto dfs = y_combinator([&](auto dfs, int v = 0, int p = -1, int d = 0, int pe = -1) -> void {
      |                                ^