QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#323123#952. Spring cleaningCamillusCompile Error//C++204.2kb2024-02-08 16:49:032024-02-08 16:49:04

Judging History

你现在查看的是最新测评结果

  • [2024-02-08 16:49:04]
  • 评测
  • [2024-02-08 16:49:03]
  • 提交

answer

/// @author Camillus
#include <bits/stdc++.h>
using namespace std;

static constexpr int maxn = 1 << 17;

vector<int> g[maxn];
int p[maxn];
int sz[maxn];
int cnt[maxn];

int root = 0;

void dfs1(int u) {
    sz[u] = 1;

    auto it = find(g[u].begin(), g[u].end(), p[u]);
    if (it != g[u].end()) g[u].erase(it);

    if (g[u].empty()) {
        cnt[u] = 1;
        return;
    }

    for (int v : g[u]) {
        p[v] = u;
        dfs1(v);
        sz[u] += sz[v];
        cnt[u] += cnt[v];
    }

    int &f = g[u].front();
    for (int &v : g[u]) {
        if (sz[v] > sz[f]) {
            swap(f, v);
        }
    }
}


int tin[maxn];
int head[maxn];
int timer = 0;

void dfs2(int u) {
    tin[u] = timer++;

    if (head[u] == 0) {
        head[u] = u;
    }

    debug(u, head[u]);

    if (!g[u].empty()) {
        head[g[u].front()] = head[u];
    }

    for (int v : g[u]) {
        dfs2(v);
    }
}

namespace st {
    using value_t = array<int, 2>;
    value_t cnt[maxn * 2 - 1];
    bool reversed[maxn];

    constexpr value_t merge(const value_t &first, const value_t &second) {
        value_t result = first;
        result[0] += second[0];
        result[1] += second[1];
        return result;
    }

    inline void apply(int x) {
        swap(cnt[x][0], cnt[x][1]);
        reversed[x] ^= 1;
    }

    inline void push(int x) {
        if (reversed[x]) {
            apply(x * 2 + 1);
            apply(x * 2 + 1);
            reversed[x] = true;
        }
    }

    void reverse(int l, int r, int x = 0, int lx = 0, int rx = maxn) {
        if (l >= rx || lx >= r) {
            return;
        }

        if (l <= lx && rx <= r) {
            apply(x);
            return;
        }

        push(x);

        reverse(l, r, x * 2 + 1, lx, (lx + rx) / 2);
        reverse(l, r, x * 2 + 2, (lx + rx) / 2, rx);

        cnt[x] = merge(cnt[x * 2 + 1], cnt[x * 2 + 2]);
    }

    value_t get(int l, int r, int x = 0, int lx = 0, int rx = maxn) {
        if (l >= rx || lx >= r) {
            return value_t();
        }

        if (l <= lx && rx <= r) {
            return cnt[x];
        }

        push(x);

        return merge(
            get(l, r, x * 2 + 1, lx, (lx + rx) / 2),
            get(l, r, x * 2 + 2, (lx + rx) / 2, rx)
        );
    }

    void build(int n) {
        for (int u = 1; u <= n; u++) {
            int x = maxn + tin[u] - 1;
            cnt[x][::cnt[u] % 2] = 1;
        }

        for (int x = maxn - 2; x >= 0; x--) {
            cnt[x] = merge(cnt[x * 2 + 1], cnt[x * 2 + 2]);
        }
    }
} // namespace st

void reverse_path(int u) {
    debug(root);
    while (true) {
        int v = head[u];

        debug(v, u);
        st::reverse(tin[v], tin[u] + 1);

        if (u == 0) {
            break;
        }

        if (u == root) {
            break;
        } else {
            u = p[u];
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int u = 1; u <= n; u++) {
        if (g[u].size() > 1) {
            root = u;
        }
    }

    dfs1(root);
    dfs2(root);

    st::build(n);

    while (q--) {
        int d;
        cin >> d;

        vector<int> a(d);
        for (int i = 0; i < d; i++) {
            cin >> a[i];
        }

        set<int> b;

        vector<int> c;

        for (int i = 0; i < d; i++) {
            int u = a[i];
            if (g[u].size() == 0 && !b.contains(u)) {
                b.insert(u);
            } else {
                reverse_path(a[i]);
                c.push_back(a[i]);
            }
        }

        auto result = st::cnt[0];

        result[1] += d;

        if (st::get(0, 1)[1]) {
            cout << -1 << '\n';
        } else {
            cout << (result[0] - 1) * 2 + result[1] << '\n';
        }

        for (int u : c) {
            reverse_path(u);
        }
    }
    return 0;
}

Details

answer.code: In function ‘void dfs2(int)’:
answer.code:52:5: error: ‘debug’ was not declared in this scope
   52 |     debug(u, head[u]);
      |     ^~~~~
answer.code: In function ‘void reverse_path(int)’:
answer.code:136:5: error: ‘debug’ was not declared in this scope
  136 |     debug(root);
      |     ^~~~~