oj.uz

Submission #237775

# Submission time Handle Problem Language Result Execution time Memory
237775 2020-06-08T17:09:08 Z kartel Usmjeri (COCI17_usmjeri) C++14
140 / 140
 533 ms 83420 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 != 0) g[v].erase(find(g[v].begin(), g[v].end(), pr));
    for (auto u : g[v]) dfs(u, v, d + 1);

    tout[v] = tim - 1;
}

int f(int x)
{
    if (pr[x] != x) pr[x] = f(pr[x]);
    return 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]);
        fnd(v = pred[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, 0, 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 (tin[v] > tin[u]) swap(v, u);
        if (tout[v] >= tout[u])
        {
            path(v, u);
        }
        else
        {
            int lc = lca(u, v);
            path(lc, v);
            path(lc, u);
            paths.pb({u, v});
        }
    }
    for (i = 1; i <= n; i++) g[i].clear();

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

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

        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 120 ms 34552 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 82472 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12416 KB Output is correct
2 Correct 12 ms 12544 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12416 KB Output is correct
2 Correct 12 ms 12544 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13056 KB Output is correct
2 Correct 14 ms 12928 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 13056 KB Output is correct
2 Correct 14 ms 12928 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 71824 KB Output is correct
2 Correct 443 ms 77032 KB Output is correct
3 Correct 236 ms 45960 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 74680 KB Output is correct
2 Correct 533 ms 82652 KB Output is correct
3 Correct 289 ms 48360 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 500 ms 75228 KB Output is correct
2 Correct 417 ms 77168 KB Output is correct
3 Correct 285 ms 48104 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 74824 KB Output is correct
2 Correct 499 ms 83420 KB Output is correct
3 Correct 208 ms 45048 KB Output is correct