Submission #235974

#	Time	Username	Problem	Language	Result	Execution time	Memory
235974		Vimmer	Usmjeri (COCI17_usmjeri)	C++14	70 / 140	667 ms	137564 KiB

usmjeri

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 300001
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef short int si;
typedef array <int, 2> a2;

//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


vector <array <int, 2> > g[N], gr[N], qr;

bool mkr[N];

int pr[N], rk[N], t[N + N][20], in[N], tin[N], id, h[N], logs[N + N], mnr[N], minr[N];

int fnd(int x) {if (pr[x] != x) pr[x] = fnd(pr[x]); return pr[x];}

void link(int x, int y)
{
    if (rk[x] < rk[y]) swap(x, y);

    pr[y] = x;

    rk[x] += rk[y];
}

vector <int> vr, to[N], glub[N], lnk[N], a[N];

ll ans = 1;

array <int, 2> pred[N];

void spusk(int v, int p)
{
    if (p != -1) h[v] = h[p] + 1; else pred[v] = {-1, -1};

    glub[h[v]].pb(v);

    in[v] = sz(vr);

    tin[v] = id++;

    vr.pb(v);

    for (auto it : g[v])
    {
        if (it[0] == p) continue;

        spusk(it[0], v);

        pred[it[0]] = {v, it[1]};

        vr.pb(v);

        gr[v].pb({tin[it[0]], it[1]});
    }

    gr[v].pb({int(1e9), int(1e9)});
}

int lca(int a, int b)
{
    if (in[a] > in[b]) swap(a, b);

    int j = logs[in[b] - in[a] + 1];

    a = t[in[a]][j];

    b = t[in[b] - (1 << j) + 1][j];

    if (h[a] > h[b]) return b;

    return a;
}

int main()
{
    //freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, m;

    cin >> n >> m;

    for (int i = 2; i < N + N; i++) logs[i] = 1 + logs[i >> 1];

    bool f = 1;

    for (int i = 0; i < n - 1; i++)
    {
        int x, y;

        cin >> x >> y;

        g[x].pb({y, i});

        g[y].pb({x, i});

        pr[i] = i;

        rk[i] = 1;
    }

    for (int i = 1; i <= n; i++) if (sz(g[i]) > 2) f = 0;

    if (f)
    {
            int beg;

            for (int i = 1; i <= n; i++) if (sz(g[i]) == 1) beg = i;

            for (; m > 0 ; m--)
            {
                int x, y;

                cin >> x >> y;

                a[x].pb(m);

                a[y].pb(m);
            }

            vector <int> vr; vr.clear();

            int v = beg, p = -1;

            while (v != -1)
            {
                int nxt = -1;

                vr.pb(v);

                for (auto it : g[v])
                {
                    if (it[0] == p) continue;

                    nxt = it[0];
                }

                p = v;

                v = nxt;
            }

            ll ans = 1;

            set <int> se; se.clear();

            for (int i = 0; i < sz(vr); i++)
            {
                bool f = 1;

                if (i != 0 && sz(se) == 0) {f = 0; ans = (ans + ans) % M;}

                for (auto it : a[vr[i]])
                {
                    if (se.find(it) == se.end()) se.insert(it);
                      else se.erase(it);
                }

                if (i != 0 && f && sz(se) == 0) ans = (ans + ans) % M;
            }
            cout << ans << endl;

            exit(0);
    }

    spusk(1, -1);

    for (int i = 0; i < sz(vr); i++) t[i][0] = vr[i];

    for (int j = 1; j < 20; j++)
        for (int i = 0; i < sz(vr); i++)
        {
            int a = t[i][j - 1];

            int b = t[min(sz(vr) - 1, i + (1 << (j - 1)))][j - 1];

            if (h[a] > h[b]) t[i][j] = b; else t[i][j] = a;
        }

    for (int i = 1; i <= n; i++) mnr[i] = -1;

    for (int i = 0; i < m; i++)
    {
        int x, y;

        cin >> x >> y;

        qr.pb({x, y});

        if (minr[x] == 0 || h[minr[x]] > h[y]) minr[x] = y;

        if (minr[y] == 0 || h[minr[y]] > h[x]) minr[y] = x;

        int lc = lca(x, y);

        if (lc == x) to[y].pb(x);
          else if (lc == y) to[x].pb(y);
            else
            {
                to[x].pb(lc);

                to[y].pb(lc);

                int pos1 = upper_bound(gr[lc].begin(), gr[lc].end(), a2{tin[x], int(1e9)}) - gr[lc].begin() - 1;

                int pos2 = upper_bound(gr[lc].begin(), gr[lc].end(), a2{tin[y], int(1e9)}) - gr[lc].begin() - 1;

                int x = fnd(gr[lc][pos1][1]), y = fnd(gr[lc][pos2][1]);

                if (x != y) link(x, y);
            }
    }

    for (auto it : qr)
    {
        int lc = lca(it[0], it[1]);

        if (minr[it[0]] != 0 && minr[it[1]] != 0 && (h[lc] > h[minr[it[0]]] && h[lc] > h[minr[it[1]]])) {cout << 0 << endl; exit(0);}
    }
    memset(mkr, 0, sizeof(mkr));

    for (int i = N - 1; i >= 0; i--)
        for (auto v : glub[i])
        {
            int root = -1;

            if (sz(lnk[v]) != 0)
            {
                root = lnk[v][0];

                for (auto it : lnk[v])
                {
                    int x = fnd(root), y = fnd(it);

                    if (x != y) link(x, y);
                }
            }

            int mn = -1;

            for (auto it : to[v])
                if (mn == -1 || h[mn] > h[it]) mn = it;

            if (mnr[v] != -1 && (mn == -1 || h[mn] > h[mnr[v]])) mn = mnr[v];

            if (mn == v || mn == -1) continue;

            int nxt = pred[v][0], nm = pred[v][1];

            if (nxt == -1) continue;

            if (mn != nxt) lnk[nxt].pb(nm);

            if (mnr[nxt] == -1 || h[mnr[nxt]] > h[mn]) mnr[nxt] = mn;

            if (mnr[v] != -1 && mnr[v] != v)
            {
                int x = fnd(root), y = fnd(nm);

                if (x != y) link(x, y);
            }
        }

    for (int i = 0; i < n - 1; i++)
    {
        int id = fnd(i);

        if (mkr[id]) continue;

        mkr[id] = 1;

        ans = (ans + ans) % M;
    }

    cout << ans << endl;
}

Compilation message (stderr)

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:146:17: warning: 'beg' may be used uninitialized in this function [-Wmaybe-uninitialized]
             int v = beg, p = -1;
                 ^

• 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: 14 / 14
• Subtask 8: 0 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14