Submission #235942

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
235942	2020-05-30T12:46:28 Z	Vimmer	Usmjeri (COCI17_usmjeri)	C++14	0 / 140	557 ms	148960 KB

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 tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


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

bool mkr[N];

int pr[N], rk[N], t[N + N][20], in[N], tin[N], tout[N], id, h[N], logs[N + N], mnr[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> path[N], vr, to[N], glub[N], lnk[N];

ll ans = 1;

array <int, 2> pred[N];

void dfser(int v, int p)
{
    mkr[v] = 1;

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

        if (mkr[it]) {cout << 0 << endl; exit(0);}

        dfser(it, v);
    }
}

void spusk(int v, int p)
{
    tin[v] = id++;

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

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

    in[v] = sz(vr);

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

    tout[v] = id++;
}

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];

    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;
    }

    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;

        path[x].pb(y);

        path[y].pb(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);}
    }

    for (int i = 1; i <= n; i++)
    {
        if (mkr[i]) continue;

        dfser(i, -1);
    }

    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;

            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;
}

Subtask #1
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	202 ms	78560 KB	Output isn't correct

Subtask #2
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	428 ms	148960 KB	Output isn't correct

Subtask #3
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	28 ms	38272 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	27 ms	38272 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	31 ms	39552 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	32 ms	39552 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	487 ms	124948 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	557 ms	125660 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	490 ms	126288 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	495 ms	125916 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Submission #235942

Compilation message