oj.uz

답안 #668003

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
668003 2022-12-02T14:12:07 Z tamthegod Usmjeri (COCI17_usmjeri) C++14
140 / 140
 442 ms 126732 KB 
#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.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 60236 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 262 ms 126732 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 24044 KB Output is correct
2 Correct 13 ms 24276 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 24148 KB Output is correct
2 Correct 14 ms 24340 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 25216 KB Output is correct
2 Correct 14 ms 25032 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 25164 KB Output is correct
2 Correct 17 ms 25044 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 391 ms 110844 KB Output is correct
2 Correct 369 ms 110992 KB Output is correct
3 Correct 235 ms 75688 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 442 ms 110756 KB Output is correct
2 Correct 422 ms 110796 KB Output is correct
3 Correct 339 ms 78572 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 404 ms 111088 KB Output is correct
2 Correct 386 ms 110988 KB Output is correct
3 Correct 267 ms 78452 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 389 ms 111400 KB Output is correct
2 Correct 370 ms 111364 KB Output is correct
3 Correct 235 ms 75560 KB Output is correct