Submission #668003

#	Time	Username	Problem	Language	Result	Execution time	Memory
668003		tamthegod	Usmjeri (COCI17_usmjeri)	C++14	140 / 140	442 ms	126732 KiB

usmjeri

#include<bits/stdc++.h>

#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 6e5 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n, m;
pair<int, int> e[maxN];
vector<int> adj[maxN];
pair<int, int> a[maxN];
int lab[maxN];
int c[maxN];
int lg[maxN], f[maxN][21];
int depth[maxN];
int Findset(int u)
{
    return lab[u] < 0 ? u : lab[u] = Findset(lab[u]);
}
void Unite(int u, int v)
{
    int r = Findset(u), s = Findset(v);
    if(r == s)
        return;
    if(lab[r] > lab[s])
        swap(r, s);
    lab[r] += lab[s];
    lab[s] = r;
}
void Log()
{
    for(int i=2; i<maxN; i++)
        lg[i] = lg[i / 2] + 1;
}
void predfs(int u, int par)
{
    for(int v : adj[u])
    {
        if(v == par)
            continue;
        f[v][0] = u;
        depth[v] = depth[u] + 1;
        for(int i=1; i<=18; i++)
            f[v][i] = f[f[v][i - 1]][i - 1];
        predfs(v, u);
    }
}
int LCA(int u, int v)
{
    if(depth[u] < depth[v])
        swap(u, v);
    int k = depth[u] - depth[v];
    for(int i=18; i>=0; i--)
    {
        if(k & (1 << i))
        {
            u = f[u][i];
            k -= (1 << i);
        }
    }
    if(u == v)
        return u;
    for(int i=18; i>=0; i--)
    {
        if(f[u][i] != f[v][i])
        {
            u = f[u][i];
            v = f[v][i];
        }
    }
    return f[u][0];
}
int jump(int x, int k)
{
    for(int i=18; i>=0; i--)
        if(k & (1 << i))
        {
            x = f[x][i];
            k -= (1 << i);
        }
    return x;
}
void ReadInput()
{
    cin >> n >> m;
    for(int i=1; i<n; i++)
    {
        int u, v;
        cin >> u >> v;
        e[i] = {u, v};
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for(int i=1; i<=m; i++)
        cin >> a[i].fi >> a[i].se;
}
int d[maxN];
void dfs(int u, int par)
{
    for(int v : adj[u])
    {
        if(v == par)
            continue;
        dfs(v, u);
        d[u] += d[v];
    }
    if(d[u] && par)
    {
        //cout << u << " ";
        Unite(u, par);
        Unite(u + n, par + n);
    }
}
int mark[maxN];
void Solve()
{
    predfs(1, 0);
    memset(lab, -1, sizeof lab);
 //   for(int i=1; i<=m; i++) cout << a[i].fi << " " << a[i].se << '\n';return;
    //cout << LCA(6, 10);return;
    for(int i=1; i<=m; i++)
    {
        int t = LCA(a[i].fi, a[i].se);
        int px = 0, py = 0;
        if(t != a[i].fi)
        {
            px = jump(a[i].fi, depth[a[i].fi] - depth[t] - 1);
            d[a[i].fi]++;
            d[px]--;
        }
        if(t != a[i].se)
        {
            py = jump(a[i].se, depth[a[i].se] - depth[t] - 1);
            d[a[i].se]++;
            d[py]--;
        }
        if(px && py)
        {
            Unite(px, py + n);
            Unite(py, px + n);
        }
      //  cout << a[i].fi << " " << a[i].se << '\n';continue;
      //  cout << t << " " << px << " " << py << '\n';
    }
    dfs(1, 0);
    int res = 1;
    for(int i=2; i<=n; i++)
    {
        if(Findset(i) == Findset(i + n))
        {
            cout << 0;
            return;
        }
        if(!mark[Findset(i)])
        {
            mark[Findset(i)] = 1;
            res *= 2;
        }
        if(!mark[Findset(i + n)])
            mark[Findset(i + n)] = 1;
        res %= mod;
    }
    cout << res;
}
int32_t main()
{
    //freopen("x.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    Log();
    ReadInput();
    Solve();
}

• 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