답안 #235753

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
235753 2020-05-29T15:10:28 Z VEGAnn Usmjeri (COCI17_usmjeri) C++14
140 / 140
685 ms 88928 KB
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair
#define ft first
#define sd second
#define PB push_back
#define pli pair<ll,int>
using namespace std;
typedef long long ll;
const int N = 300100;
const int PW = 20;
const int oo = 2e9;
const int md = int(1e9) + 7;
vector<int> g[N], chk[N];
queue<int> q;
int n, m, pr[N], ans = 1, up[N][PW], tin[N], tout[N], tt = 0, ad[N];
int V[N], NM[N], U[N], LC[N], fen[2][N], h[N], col[N], p1[N], p2[N];
bool mrk[N], chkd[N];

int get(int x) { return (pr[x] == x ? x : pr[x] = get(pr[x])); }

void dfs(int v, int p){
    up[v][0] = p;

    for (int po = 1; po < PW; po++)
        up[v][po] = up[up[v][po - 1]][po - 1];

    tin[v] = ++tt;

    for (int u : g[v]){
        if (p == u) continue;

        h[u] = h[v] + 1;
        dfs(u, v);
    }

    tout[v] = tt;
}

bool upper(int a, int b){
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}

int lca(int a, int b){
    if (upper(a, b)) return a;
    if (upper(b, a)) return b;

    for (int po = PW - 1; po >= 0; po--)
        if (!upper(up[a][po], b))
            a = up[a][po];

    return up[a][0];
}

int pra(int a, int b){
    for (int po = PW - 1; po >= 0; po--)
        if (!upper(up[a][po], b))
            a = up[a][po];

    return a;
}

void DFS(int v){
    for (int u : g[v]){
        if (u == up[v][0]) continue;

        DFS(u);

        ad[v] += ad[u];
    }

    if (ad[v] > 0)
        pr[get(v)] = get(up[v][0]);
}

bool cmp(int _x, int _y){
    if (h[LC[_x]] == h[LC[_y]])
        return min(tin[U[_x]], tin[V[_x]]) < min(tin[U[_y]], tin[V[_y]]);
    return h[LC[_x]] < h[LC[_y]];
}

int sum(int tp, int ps){
    int res = 0;

    for (; ps >= 0; ps = (ps & (ps + 1)) - 1)
        res += fen[tp][ps];

    return res;
}

void update(int tp, int ps, int vl){
    for (; ps < N; ps = (ps | (ps + 1)))
        fen[tp][ps] += vl;
}

void BAD(){
    cout << 0;
    exit(0);
}

void upd(int cl, int v, int lc){
    while (col[v] < 0 && v != lc) {
        update(cl, tin[v], 1);
        update(cl, tout[v] + 1, -1);
        col[v] = cl;
        v = up[v][0];
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m;

    for (int i = 1; i < n; i++){
        int x, y; cin >> x >> y;
        x--; y--;

        g[x].PB(y);
        g[y].PB(x);

        pr[i] = i;
        col[i] = -1;
    }

    dfs(0, 0);

    for (int i = 0; i < m; i++){
        int x, y; cin >> x >> y;
        x--; y--;

        int lc = lca(x, y);

        LC[i] = lc;
        NM[i] = i;

        if (x != lc)
            swap(x, y);

        U[i] = x; V[i] = y;

        if (x == lc){
            ad[y]++;
            int PR = pra(y, x);
            ad[PR]--;
            p1[i] = PR;
        } else {
            ad[x]++;
            ad[y]++;
            int pr1 = pra(x, y);
            int pr2 = pra(y, x);
            ad[pr1]--;
            ad[pr2]--;

            pr[pr1] = get(pr2);

            p1[i] = pr1;
            p2[i] = pr2;
        }
    }

    DFS(0);

    sort(NM, NM + m, cmp);

    for (int i = 1; i < n; i++){
        int cur = get(i);

        if (mrk[cur]) continue;

        mrk[cur] = 1;

        ans += ans;

        if (ans >= md)
            ans -= md;
    }

    fill(mrk, mrk + n, 0);
    fill(chkd, chkd + n, 0);

    for (int it = 0; it < m; ){
        int j = it;

        while (j < m && LC[NM[j]] == LC[NM[it]]) {
            int i = NM[j];

            if (U[i] == LC[i]){
                chk[p1[i]].PB(i);
            } else {
                chk[p1[i]].PB(i);
                chk[p2[i]].PB(i);
            }
            j++;
        }

        int lc = LC[NM[it]];

        for (int u : g[lc]){
            if (u == up[lc][0]) continue;

            if (mrk[u]) continue;

            q.push(u);
            mrk[u] = 1;

            while (sz(q)){
                int v = q.front(); q.pop();

                for (int i : chk[v]){
                    if (chkd[i]) continue;

                    chkd[i] = 1;

                    if (U[i] != LC[i]){
                        int nw = (p1[i] == v ? p2[i] : p1[i]);

                        if (!mrk[nw]){
                            mrk[nw] = 1;
                            q.push(nw);
                        }
                    }

                    if (U[i] == LC[i]){
                        int sf = sum(0, tin[V[i]]) - sum(0, tin[LC[i]]);
                        int ss = sum(1, tin[V[i]]) - sum(1, tin[LC[i]]);

                        if (sf > 0 && ss > 0)
                            BAD();

                        if (ss == 0){
                            upd(0, V[i], LC[i]);
                        } else {
                            upd(1, V[i], LC[i]);
                        }
                    } else {
                        int ff = sum(0, tin[U[i]]) - sum(0, tin[LC[i]]);
                        int fs = sum(1, tin[U[i]]) - sum(1, tin[LC[i]]);

                        int sf = sum(0, tin[V[i]]) - sum(0, tin[LC[i]]);
                        int ss = sum(1, tin[V[i]]) - sum(1, tin[LC[i]]);

                        if (ff > 0 && fs > 0)
                            BAD();

                        if (sf > 0 && ss > 0)
                            BAD();

                        if (sf > 0 && ff > 0)
                            BAD();

                        if (ss > 0 && fs > 0)
                            BAD();

                        if (ff == 0 && sf == 0){
                            if (ss > 0) {
                                upd(1, V[i], LC[i]);
                                upd(0, U[i], LC[i]);
                            } else {
                                upd(0, V[i], LC[i]);
                                upd(1, U[i], LC[i]);
                            }
                        } else {
                            if (ff == 0) {
                                upd(0, V[i], LC[i]);
                                upd(1, U[i], LC[i]);
                            } else {
                                upd(1, V[i], LC[i]);
                                upd(0, U[i], LC[i]);
                            }
                        }
                    }
                }
            }
        }

        it = j;
    }

    cout << ans;

    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 216 ms 43308 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 395 ms 88928 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 14848 KB Output is correct
2 Correct 13 ms 14848 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 14848 KB Output is correct
2 Correct 15 ms 14976 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 15616 KB Output is correct
2 Correct 15 ms 15360 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 15616 KB Output is correct
2 Correct 16 ms 15360 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 540 ms 72320 KB Output is correct
2 Correct 604 ms 72520 KB Output is correct
3 Correct 322 ms 49616 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 685 ms 74020 KB Output is correct
2 Correct 653 ms 73796 KB Output is correct
3 Correct 426 ms 54508 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 641 ms 74140 KB Output is correct
2 Correct 574 ms 72564 KB Output is correct
3 Correct 436 ms 54248 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 597 ms 74340 KB Output is correct
2 Correct 607 ms 74724 KB Output is correct
3 Correct 290 ms 48120 KB Output is correct