oj.uz

Submission #201046

# Submission time Handle Problem Language Result Execution time Memory
201046 2020-02-09T08:13:50 Z SamAnd Usmjeri (COCI17_usmjeri) C++17
140 / 140
 714 ms 88492 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 300005, M = 1000000007;

int n, qq;
vector<int> a[N];

const int m = 20;
int p[N][m];

int tin[N], tout[N], ti;

void dfs(int x, int pp)
{
    tin[x] = ++ti;
    p[x][0] = pp;
    for (int i = 1; i < m; ++i)
        p[x][i] = p[p[x][i - 1]][i - 1];
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (h == pp)
            continue;
        dfs(h, x);
    }
    tout[x] = ti;
}

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

int go(int x, int y)
{
    for (int i = m - 1; i >= 0; --i)
    {
        if (!isp(p[x][i], y))
            x = p[x][i];
    }
    return x;
}

int q[N];

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

void dfs1(int x, int pp)
{
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (h == pp)
            continue;
        dfs1(h, x);
        q[x] += q[h];
    }
    if (q[x])
    {
        g[x].push_back({pp, 0});
        g[pp].push_back({x, 0});
    }
}

int c[N];

bool dfs2(int x, int z)
{
    c[x] = z;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i].first;
        if (g[x][i].second)
        {
            if (!c[h])
            {
                if (!dfs2(h, ((z - 1) ^ 1) + 1))
                    return false;
            }
            else
            {
                if (c[x] == c[h])
                    return false;
            }
        }
        else
        {
            if (!c[h])
            {
                if (!dfs2(h, z))
                    return false;
            }
            else
            {
                if (c[x] != c[h])
                    return false;
            }
        }
    }
    return true;
}

int main()
{
    scanf("%d%d", &n, &qq);
    for (int i = 0; i < n - 1; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1, 1);
    for (int i = 0; i < qq; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if (isp(x, y))
        {
            ++q[y];
            --q[go(y, x)];
            continue;
        }
        if (isp(y, x))
        {
            ++q[x];
            --q[go(x, y)];
            continue;
        }
        ++q[x];
        --q[go(x, y)];
        ++q[y];
        --q[go(y, x)];
        g[x].push_back({y, 1});
        g[y].push_back({x, 1});
    }
    dfs1(1, 1);
    int ans = 1;
    for (int x = 2; x <= n; ++x)
    {
        if (!c[x])
        {
            if (!dfs2(x, 1))
            {
                printf("0\n");
                return 0;
            }
            ans = (ans * 2) % M;
        }
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message

usmjeri.cpp: In function 'void dfs(int, int)':
usmjeri.cpp:19:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
usmjeri.cpp: In function 'void dfs1(int, int)':
usmjeri.cpp:50:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
usmjeri.cpp: In function 'bool dfs2(int, int)':
usmjeri.cpp:70:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
usmjeri.cpp: In function 'int main()':
usmjeri.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &qq);
     ~~~~~^~~~~~~~~~~~~~~~~
usmjeri.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
usmjeri.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 40696 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 88492 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14584 KB Output is correct
2 Correct 16 ms 14712 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14584 KB Output is correct
2 Correct 16 ms 14712 KB Output is correct

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

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

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 63432 KB Output is correct
2 Correct 668 ms 65336 KB Output is correct
3 Correct 340 ms 46968 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 714 ms 67576 KB Output is correct
2 Correct 680 ms 67452 KB Output is correct
3 Correct 447 ms 51068 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 688 ms 68264 KB Output is correct
2 Correct 600 ms 64400 KB Output is correct
3 Correct 465 ms 50936 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 656 ms 68728 KB Output is correct
2 Correct 645 ms 68984 KB Output is correct
3 Correct 354 ms 47736 KB Output is correct