Submission #433192

#	Time	Username	Problem	Language	Result	Execution time	Memory
433192		blue	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	138 ms	262148 KiB

oneway

#include <iostream>
#include <vector>
using namespace std;

int N, M;
vector<int> edge[300000+1];
int anc[300000+1][20];
int depth[300000+1];
vector<int> score(300000+1, 0);
vector<int> newGraph[300000+1];

void dfs(int u)
{
    for(int v: edge[u])
    {
        if(anc[u][0] == v) continue;
        anc[v][0] = u;
        depth[v] = depth[u] + 1;
        dfs(v);
    }
}

int lca(int u, int v)
{
    if(depth[u] < depth[v]) swap(u, v);
    int d = depth[u] - depth[v];
    for(int j = 0; j < 20; j++) if(d & (1 << j)) u = anc[u][j];
    if(u == v) return u;
    for(int j = 19; j >= 0; j--) if(anc[u][j] != anc[v][j])
    {
        u = anc[u][j];
        v = anc[v][j];
    }
    newGraph[u].push_back(-v);
    newGraph[v].push_back(-u);
    return anc[u][0];
}

void dfs2(int u)
{
    for(int v: edge[u]) if(v != anc[u][0])
    {
        dfs2(v);
        if(0 < score[v])
        {
            newGraph[u].push_back(v);
            newGraph[v].push_back(u);
        }
        score[u] = max(score[u], score[v] - 1);
    }
}

int cc = 0;
vector<int> orient(300000+1, 0);

bool impossible = 0;

void newdfs(int u)
{
    for(int v: newGraph[u])
    {
        if(v < 0)
        {
            if(orient[-v] == orient[u])
            {
                impossible = 1;
                return;
            }
            else if(orient[-v] == -orient[u]) continue;
            else
            {
                orient[-v] = -orient[u];
                newdfs(-v);
            }
        }
        else
        {
            if(orient[v] == -orient[u])
            {
                impossible = 1;
                return;
            }
            else if(orient[v] == orient[u]) continue;
            else
            {
                orient[v] = orient[u];
                newdfs(v);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    int a, b;
    for(int i = 1; i <= N-1; i++)
    {
        cin >> a >> b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    anc[1][0] = 1;
    depth[1] = 0;
    dfs(1);
    for(int j = 1; j < 20; j++)
    {
        for(int i = 1; i <= N; i++)
        {
            anc[i][j] = anc[ anc[i][j-1] ][j-1];
        }
    }
    int L;
    for(int i = 1; i <= M; i++)
    {
        cin >> a >> b;
        L = lca(a, b);
        score[b] = max(score[b], depth[b] - depth[L] - 1);
        score[a] = max(score[a], depth[a] - depth[L] - 1);
    }
    dfs2(1);

    for(int i = 2; i <= N; i++)
    {
        if(orient[i] != 0) continue;
        orient[i] = 1;
        cc++;
        newdfs(i);
    }

    if(impossible)
    {
        cout << "0\n";

        return 0;
    }

    int res = 1;
    for(int i = 1; i <= cc; i++) res = (res * 2) % 1000000007;

    cout << res << '\n';

    return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40