oj.uz

Submission #85601

# Submission time Handle Problem Language Result Execution time Memory
85601 2018-11-21T04:12:16 Z tieunhi Usmjeri (COCI17_usmjeri) C++14
140 / 140
 589 ms 72400 KB 
#include <bits/stdc++.h>
#define pii pair<ll, ll>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define ll long long
#define N 300005
#define LN 21
#define maxc 1000000000000000007

using namespace std;

int n, m, h[N], high[N], p[N][LN], dd[N];
vector<int> a[N];
vector<pii> g[N];

void setup()
{
    cin >> n >> m;
    FOR(i, 2, n)
    {
        int u, v; cin >> u >> v;
        a[u].PB(v);
        a[v].PB(u);
    }
}
void preDFS(int u)
{
    for (auto v : a[u])
    {
        if (v == p[u][0]) continue;
        p[v][0] = u;
        h[v] = h[u] + 1;
        FOR(i, 1, LN-1)
            p[v][i] = p[p[v][i-1]][i-1];
        preDFS(v);
    }
}
int LCA(int u, int v)
{
    if (h[u] > h[v]) swap(u, v);
    int delta = h[v] - h[u];
    FOR(i, 0, LN-1)
        if ((delta >> i) & 1) v = p[v][i];
    if (u == v) return u;
    FORD(i, LN-1, 0)
        if (p[u][i] != p[v][i])
        {
            u = p[u][i];
            v = p[v][i];
        }
    return p[u][0];
}
void add_edge(int u, int v, int val)
{
    g[u].PB(mp(v, val));
    g[v].PB(mp(u, val));
}
int connect(int u)
{
    for (auto v : a[u])
    {
        if (v == p[u][0]) continue;
        int temp = connect(v);
        high[u] = min(temp, high[u]);
        if (temp < h[u])
            add_edge(u, v, 0);
    }
    return high[u];
}
int DFS(int u, int val)
{
    if (dd[u] != -1)
        return dd[u] == val;
    dd[u] = val;
    for (auto z : g[u])
    {
        int v = z.F;
        int w = z.S;
        if (!DFS(v, val^w)) return 0;
    }
    return 1;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    setup();
    preDFS(1);
    FOR(i, 1, n) high[i] = h[i];
    while (m--)
    {
        int u, v; cin >> u >> v;
        int lca= LCA(u, v);
        high[u] = min(high[u], h[lca]);
        high[v] = min(high[v], h[lca]);
        if (u != lca && v != lca)
            add_edge(u, v, 1);
    }
    connect(1);
    memset(dd, -1, sizeof dd);
    int res = 1;
    FOR(i, 2, n)
        if (dd[i] == -1)
        {
            if (!DFS(i, 0))
                res = 0;
            else res = (res*2) % 1000000007;
        }
    cout <<res;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 35576 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 72400 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 72400 KB Output is correct
2 Correct 19 ms 72400 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 72400 KB Output is correct
2 Correct 17 ms 72400 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 72400 KB Output is correct
2 Correct 20 ms 72400 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 72400 KB Output is correct
2 Correct 20 ms 72400 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 72400 KB Output is correct
2 Correct 514 ms 72400 KB Output is correct
3 Correct 327 ms 72400 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 72400 KB Output is correct
2 Correct 546 ms 72400 KB Output is correct
3 Correct 379 ms 72400 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 72400 KB Output is correct
2 Correct 490 ms 72400 KB Output is correct
3 Correct 387 ms 72400 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 72400 KB Output is correct
2 Correct 528 ms 72400 KB Output is correct
3 Correct 364 ms 72400 KB Output is correct