Submission #201046

#	Time	Username	Problem	Language	Result	Execution time	Memory
201046		SamAnd	Usmjeri (COCI17_usmjeri)	C++17	140 / 140	714 ms	88492 KiB

usmjeri

#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 (stderr)

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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14