oj.uz

Submission #237767

# Submission time Handle Problem Language Result Execution time Memory
237767 2020-06-08T16:47:13 Z kartel Usmjeri (COCI17_usmjeri) C++14
28 / 140
 528 ms 89568 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define N +500500
#define MaxS N * N
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
//#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;

int pred[N], pr[N], ra[N], tin[N], tout[N], de[N], up[N][23], col[N];
bool mk[N];

vector <pair <int, int> > paths;
vector <int> g[N];

int n, m, i, bad = 0, j, x, y, v, u, tim;
ll ans;

int ispred(int x, int y) {return (tin[x] <= tin[y] && tout[x] >= tout[y]);}

int lca(int x, int y)
{
    for (int st = 20; st >= 0; st--)
        if (!ispred(up[x][st], y))
          x = up[x][st];
    return up[x][0];
}

void dfs(int v, int pr, int d)
{
    tin[v] = tim++;
    de[v] = d;

    up[v][0] = pr;
    pred[v] = pr;

    if (pr != -1) g[v].erase(find(g[v].begin(), g[v].end(), pr));
    for (auto u : g[v]) dfs(u, v, d + 1);

    tout[v] = tim++;
}

int f(int x) {return ((pr[x] == x) ? x : (pr[x] = f(pr[x])));}
void link(int x, int y) {pr[f(x)] = f(y);}

void check(int v, int c)
{
    if (mk[v] && col[v] != c) bad = 1;
    if (mk[v]) return;

    mk[v] = 1;
    col[v] = c;

    for (auto u : g[v]) check(u, c ^ 1);
}

void fnd(int v)
{
    if (v == 1) return;

    if (f(v) == f(pred[v]))
    {
        fnd(pred[v]);
        pred[v] = pred[pred[v]];
    }
}

void path(int v, int u)
{
    swap(v, u);
    fnd(v);
    while (de[u] < de[pred[v]])
    {
        link(v, pred[v]);
        v = pred[v];
        fnd(v);
    }
}


int main()
{
    srand(time(0));
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

//    in("input.txt");
//    out("output.txt");

    cin >> n >> m;
    for (i = 1; i <= n; i++) g[i].clear(), pr[i] = i, ra[i] = 1;

    for (i = 1; i < n; i++)
    {
        cin >> v >> u;
        g[v].pb(u);
        g[u].pb(v);
    }

    tim = 1;
    tin[0] = -1;
    tout[0] = N;

    dfs(1, -1, 0);

    for (int st = 1; st <= 20; st++)
      for (i = 1; i <= n; i++) up[i][st] = up[up[i][st - 1]][st - 1];

    for (i = 1; i <= m; i++)
    {
        cin >> v >> u;
        if (u == v) continue;
        if (ispred(v, u))
        {
            path(v, u);
        }
        else if (ispred(u, v))
        {
            path(u, v);
        }
        else
        {
            int lc = lca(u, v);
            path(lc, v);
            path(lc, u);
            paths.pb({u, v});
        }
    }

    for (auto x : paths)
    {
        int v = f(x.F);
        int u = f(x.S);

        if (v == u) {cout << "0";return 0;}

        g[v].pb(u);
        g[u].pb(v);
    }

    bad = 0;
    for (i = 2; i <= n; i++)
        if (!mk[i])
            check(i, 0);

    if (bad) {cout << "0";return 0;}

    for (auto x : paths) link(x.F, x.S);

    set <int> se;
    for (i = 2; i <= n; i++) se.insert(f(i));

    ans = 1;
    for (i = 0; i < sz(se); i++) ans = (ans << 1ll) % M;

    cout << ans;

}

//  x ^ 2 + y ^ 2 = 1
//  x * a_i + y * b_i
//  a_i = -b_i * tan(alpha)
//  a_i / -b_i = tan(alpha)
//  alpha = atan(a_i / (-b_i))

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 37884 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 89568 KB Output is correct

Subtask #3
0 / 14.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 14.0

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

Subtask #6
0 / 14.0

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

Subtask #7
0 / 14.0

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

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

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