Submission #85601

#	Time	Username	Problem	Language	Result	Execution time	Memory
85601		tieunhi	Usmjeri (COCI17_usmjeri)	C++14	140 / 140	589 ms	72400 KiB

usmjeri

#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 / 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