QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#64846#4814. Exciting Travelckiseki#WA 4ms9604kbC++177.8kb2022-11-25 19:10:502022-11-25 19:10:52

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-25 19:10:52]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:9604kb
  • [2022-11-25 19:10:50]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
static constexpr int maxn = 2'000'00 + 5;
static constexpr int kLog = 19;


static constexpr inline int lowbit(int x) { return x & (-x); }

class LBD {
    int tc, chains;
    vector<vector<int>> G;
    vector<int> tl, tr, chain, head, dep, pa;
    void predfs(int u, int f) {
        dep[u] = dep[pa[u] = f] + 1;
        for (int v : G[u]) if (v != f) {
            predfs(v, u);
            if (lowbit(chain[u]) < lowbit(chain[v]))
                chain[u] = chain[v];
        }
        if (chain[u] == 0) chain[u] = ++chains;
    }
    void dfschain(int u, int f) {
        tl[u] = tc++;
        if (head[chain[u]] == -1)
            head[chain[u]] = u;
        for (int v : G[u])
            if (v != f and chain[v] == chain[u])
                dfschain(v, u);
        for (int v : G[u])
            if (v != f and chain[v] != chain[u])
                dfschain(v, u);
        tr[u] = tc;
    }
public:
    LBD(int n) : tc(0), chains(0), G(n), tl(n), tr(n), chain(n), head(n, -1), dep(n), pa(n) {}
    void add_edge(int u, int v) {
        G[u].push_back(v);
        G[v].push_back(u);
    }
    void decompose() {
        predfs(0, 0);
        dfschain(0, 0);
    }
    pair<int, int> get_subtree(int u) const {
        return {tl[u], tr[u]};
    }
    vector<pair<int, int>> get_path(int u, int v) {
        vector<pair<int, int>> res;
        while (chain[u] != chain[v]) {
            if (dep[head[chain[u]]] < dep[head[chain[v]]])
                swap(u, v);
            int s = head[chain[u]];
            res.emplace_back(tl[s], tl[u] + 1);
            u = pa[s];
        }
        if (dep[u] < dep[v]) swap(u, v);
        res.emplace_back(tl[v], tl[u] + 1);
        return res;
    }
};

class BIT {
    vector<int> b;
    int query(int p) {
        int r = 0;
        while (p) {
            r += b[p];
            p -= lowbit(p);
        }
        return r;
    }
public:
    BIT(int n) : b(n) {}
    void add(int p, int x) {
        while (p < int(b.size())) {
            b[p] += x;
            p += lowbit(p);
        }
    }
    int query(int l, int r) {
        // cerr << "> query(" << l << ", " << r << "] @ " << b.size() << endl;
        return query(r) - query(l);
    }
};

class DS : public LBD {
    BIT bit;
public:
    DS(int n) : LBD(n), bit(n + 1) {}
    // void add_edge(int, int);
    // void decompose();
    void add(int u, int x) {
        auto [p, _] = get_subtree(u);
        bit.add(p + 1, x);
    }
    int query(int u, int v) {
        int s = 0;
        for (auto [l, r] : get_path(u, v))
            s += bit.query(l, r);
        return s;
    }
};

int pa[maxn][kLog];
vector<int> g[maxn];

int tin[maxn], tout[maxn], tc;

bool anc(int u, int v) {
    return tin[u] <= tin[v] and tout[v] <= tout[u];
}

int lca(int u, int v) {
    if (anc(u, v)) return u;
    for (int i = kLog - 1; i >= 0; --i)
        if (not anc(pa[u][i], v))
            u = pa[u][i];
    return pa[u][0];
}

void dfs(int u, int f) {
    pa[u][0] = f;
    for (int i = 1; i < kLog; ++i)
        pa[u][i] = pa[pa[u][i - 1]][i - 1];

    tin[u] = tc++;
    for (int v : g[u]) {
        if (v == f) continue;
        dfs(v, u);
    }
    tout[u] = tc;
}


vector<pair<int, int>> get_tree(vector<int> vs, int r = 0) {
    vector<pair<int, int>> res;
    sort(vs.begin(), vs.end(), [](int i, int j) {
        return tin[i] < tin[j];
    });
    vs.erase(unique(vs.begin(), vs.end()), vs.end());
    vector<int> s = {r};
    for (int v : vs) if (v != r) {
        if (int o = lca(v, s.back()); o != s.back()) {
            while (s.size() >= 2) {
                if (tin[s[s.size() - 2]] < tin[o])
                    break;
                res.emplace_back(s[s.size() - 2], s.back());
                s.pop_back();
            }
            if (s.back() != o) {
                res.emplace_back(o, s.back());
                s.back() = o;
            }
        }
        s.push_back(v);
    }
    for (size_t i = 1; i < s.size(); ++i)
        res.emplace_back(s[i - 1], s[i]);
    return res;
}

pair<int, int> shrink(int u, int v) {
    if (u == v) {
        return {-1, -1};
    }
#define chk() if (anc(u, v)) {\
        if (pa[v][0] == u) \
            return {-1, -1}; \
        int o = pa[v][0];\
        for (int i = kLog - 1; i >= 0; --i) \
            if (not anc(pa[v][i], u)) v = pa[v][i]; \
        return {o, v}; \
    }
    chk();
    swap(u, v);
    chk();
    return {pa[v][0], pa[u][0]};
}

int main() {
#ifdef CKISEKI
    freopen("e.3.in", "r", stdin);
#endif

    cin.tie(nullptr)->sync_with_stdio(false);
    int N, Q; cin >> N >> Q;
    DS allds(N);
    for (int i = 1; i < N; ++i) {
        int u, v; cin >> u >> v;
        --u, --v;
        allds.add_edge(u, v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(0, 0);

    allds.decompose();

    vector<vector<int>> vt(N);
    vector<int> ID(N, -1);

    // for (int i = 0; i < Q; i++) {
    while (Q--) {
        int k;
        cin >> k;
        if (k == 1) {
            cout << "0\n";
            continue;
        }
        vector<int> x(k);
        for (int j = 0; j < k; j++) {
            cin >> x[j];
            --x[j];
            allds.add(x[j], 1);
        }
        int adj = 0;

        vector<pair<int,int>> path(k);
        vector<int> vtx = x;
        for (int j = 1; j < k; j++) {
            path[j] = shrink(x[j-1], x[j]);
            auto &[a, b] = path[j];
            // cerr << "x[j-1], x[j] = " << x[j-1] << ", " << x[j] << endl;
            // cerr << "a, b = " << a << ", " << b << endl;
            if (a == -1) {
                // adjacent
                // cerr << "ADJ " << a << ", " << b << endl;
                ++adj;
                continue;
            }
            if (allds.query(a, b) != 0) {
                // cerr << "HAS VTX " << a << ", " << b << endl;
                // yang
                a = b = -1;
                continue;
            }
            vtx.emplace_back(a);
            vtx.emplace_back(b);
        }

        const auto vt_edges = get_tree(vtx);

        for (const auto [u, v]: vt_edges)
            ID[u] = ID[v] = -1;
        int curID = 0;
        for (const auto [u, v]: vt_edges) {
            if (ID[u] == -1) ID[u] = curID++;
            if (ID[v] == -1) ID[v] = curID++;
        }
        
        // cerr << "curID = " << curID << endl;
        DS ds(curID);

        for (const auto [u, v]: vt_edges) {
            // cerr << ID[u] << "(" << u+1 << ")"
            //     << " -> " << ID[v] << "(" << v+1 << ")" << endl;
            ds.add_edge(ID[u], ID[v]);
            vt[ID[u]].emplace_back(ID[v]);
        }
        ds.decompose();
        // cerr << "-----\n";

        // cerr << "ID[0] = " << ID[0] << endl;

        vector<vector<pair<int,int>>> paths(curID);
        
        for (int j = 1; j < k; j++) {
            auto [a, b] = path[j];
            if (a == -1) continue;
            int c = lca(a, b);
            // cerr << "PATH " << ID[c] << ' ' << ID[a] << ' ' << ID[b] << endl;
            paths[ID[c]].emplace_back( ID[a], ID[b] );
        }

        vector<int> dp(curID);
        const auto dfs_vt = [&](auto self, int i) -> void {
            int sum = 0;
            for (int j: vt[i]) {
                self(self, j);
            }
            for (int j: vt[i])
                sum += dp[j];
            dp[i] = sum;
            for (auto [a, b]: paths[i]) {
                dp[i] = max(dp[i], ds.query(a, b) + 1);
            }
            ds.add(i, sum);
            // cerr << "i, dp[i] = " << i+1 << ' ' << dp[i] << endl;
        };

        // cerr << "ID[root] = " << ID[0] << endl;
        dfs_vt(dfs_vt, ID[0]);

        int ans = *max_element(dp.begin(), dp.end());

        cout << k - 1 - ans - adj << '\n';

        for (int j = 0; j < k; j++) {
            allds.add(x[j], -1);
        }
        for (const auto [u, v]: vt_edges) {
            // paths[ID[u]].clear();
            // paths[ID[v]].clear();
            vt[ID[u]].clear();
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 9604kb

input:

5 3
1 2
1 3
2 4
2 5
3 1 4 5
4 1 2 4 3
4 2 4 5 1

output:

1
1
2

result:

ok 3 number(s): "1 1 2"

Test #2:

score: -100
Wrong Answer
time: 3ms
memory: 8452kb

input:

8 7
1 2
1 3
1 4
2 5
2 6
5 7
3 8
1 4
2 1 7
3 5 2 4
4 3 6 1 4
6 5 3 7 1 2 4
6 4 8 3 5 6 1
7 2 8 5 4 6 1 3

output:

0
2
2
0
2
0
0

result:

wrong answer 2nd numbers differ - expected: '0', found: '2'