QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#116176#4814. Exciting TravelHaccerKatWA 4ms31312kbC++2010.2kb2023-06-28 11:23:252023-06-28 11:23:28

Judging History

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

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

answer

#include <bits/stdc++.h>
using namespace std;
template<typename T>
int SIZE(T (&t)){
    return t.size();
}

template<typename T, size_t N>
int SIZE(T (&t)[N]){
    return N;
}

string to_string(char t){
    return "'" + string({t}) + "'";
}

string to_string(bool t){
    return t ? "true" : "false";
}

string to_string(const string &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)), _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += t[i];
    }
    return '"' + ret + '"';
}

string to_string(const char* t){
    string ret(t);
    return to_string(ret);
}

template<size_t N>
string to_string(const bitset<N> &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)); i <= min(x2,SIZE(t)-1); ++i){
        ret += t[i] + '0';
    }
    return to_string(ret);
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1=0, int x2=1e9, Coords... C);

template<typename T, typename S>
string to_string(const pair<T, S> &t){
    return "(" + to_string(t.first) + ", " + to_string(t.second) + ")";
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1, int x2, Coords... C){
    string ret = "[";
    x1 = min(x1, SIZE(t));
    auto e = begin(t);
    advance(e,x1);
    for(int i = x1, _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += to_string(*e, C...) + (i != _i ? ", " : "");
        e = next(e);
    }
    return ret + "]";
}

template<int Index, typename... Ts>
struct print_tuple{
    string operator() (const tuple<Ts...>& t) {
        string ret = print_tuple<Index - 1, Ts...>{}(t);
        ret += (Index ? ", " : "");
        return ret + to_string(get<Index>(t));
    }
};

template<typename... Ts>
struct print_tuple<0, Ts...> {
    string operator() (const tuple<Ts...>& t) {
        return to_string(get<0>(t));
    }
};

template<typename... Ts>
string to_string(const tuple<Ts...>& t) {
    const auto Size = tuple_size<tuple<Ts...>>::value;
    return print_tuple<Size - 1, Ts...>{}(t);
}

void dbgr(){;}
template<typename Heads, typename... Tails>
void dbgr(Heads H, Tails... T){
    cout << to_string(H) << " | ";
    dbgr(T...);
}

void dbgs(){;}
template<typename Heads, typename... Tails>
void dbgs(Heads H, Tails... T){
    cout << H << " ";
    dbgs(T...);
}

/*
formatted functions:
*/

/*
consider __VA_ARGS__ as a whole:
dbgv() prints values only
dbg() prints name and values
*/
#define dbgv(...) cout << to_string(__VA_ARGS__) << endl;

#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgv(__VA_ARGS__);
//#define dbg(...)

/*
consider __VA_ARGS__ as a sequence of arguments:
dbgr() prints values only
dbgm() prints names and values
*/
#define dbgr(...) dbgr(__VA_ARGS__); cout << endl;

#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgr(__VA_ARGS__);

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
// using u128 = __uint128_t;
// using i128 = __int128;
const int mod = 1000000007;
const int N = 200005;
const int LOG = 20;
const int inf = 1e9;
const double eps = 1e-11;
template <typename T>
struct BIT {
    T bit[N * 2];
    stack<pair<int, T>> changes;
    void update(int p, T x, bool reset = false) {
        if (!reset) changes.push({p, x});
        for (; p < N * 2; p += p & (-p)) {
            bit[p] += x;
        }
    }
    
    T query(int p) {
        T res = 0;
        for (; p > 0; p -= p & (-p)) {
            res += bit[p];
        }
        
        return res;
    }
    
    T query(T l, T r) {
        return query(r) - query(l - 1);
    }
    
    void reset() {
        while (!changes.empty()) {
            auto [p, x] = changes.top();
            changes.pop();
            update(p, -x, true);
        }
    }
};

int n, m, k, qq;
vector<int> adj[N], adjvir[N];
int dep[N], tin[N], tin2[N], tout2[N];
int rmq[N * 2][LOG], rmqmn[N * 2][LOG], logA[N * 2];
bool vis[N];
int timer = 0, timer2 = 1;
vector<int> order;
void dfs(int u) {
    vis[u] = true, tin[u] = timer++, tin2[u] = timer2++;
    order.push_back(u);
    for (int v : adj[u]) {
        if (!vis[v]) {
            dep[v] = dep[u] + 1;
            dfs(v);
            order.push_back(u);
            timer++;
        }
    }
    
    tout2[u] = timer2++;
}

void precomp() {
    int sz = order.size();
    for (int i = 2; i <= sz; i++) logA[i] = logA[i >> 1] + 1;
    for (int i = 0; i < sz; i++) {
        int u = order[i];
        rmq[i][0] = u, rmqmn[i][0] = dep[u];
    }
    
    for (int j = 1; j < LOG; j++) {
        for (int i = 0; i + (1 << j) <= sz; i++) {
            int x = (1 << j - 1);
            int lx = rmqmn[i][j - 1], rx = rmqmn[i + x][j - 1];
            rmqmn[i][j] = min(lx, rx);
            rmq[i][j] = (lx < rx ? rmq[i][j - 1] : rmq[i + x][j - 1]);
        }
    }
}

int getlca(int u, int v) {
    int l = tin[u], r = tin[v];
    if (l > r) swap(l, r);
    int len = r - l + 1;
    int lg = logA[len], x = 1 << lg;
    int lx = rmqmn[l][lg], rx = rmqmn[r - x + 1][lg];
    return (lx < rx ? rmq[l][lg] : rmq[r - x + 1][lg]);
}

BIT<int> b;
void update(int u, int x) {
    int l = tin2[u], r = tout2[u];
    b.update(l, x);
    b.update(r, -x);
}

int query(int u, int v) {
    int lca = getlca(u, v);
    int ut = tin2[u], lcat = tin2[lca], vt = tin2[v];
    return b.query(lcat, ut) + b.query(lcat, vt) - b.query(lcat, lcat);
}

vector<pi> edges[N];
// vector<map<int, int>> mp;
int dp[N], pos[N], cntpaths[N];
void dfs2(int u) {
    int x = 0;
    for (int v : adjvir[u]) {
        dfs2(v);
        x += dp[v];
    }
    
    update(u, x);
    auto findbest = [&](int u, int v, int d = -1, bool upd = false) {
        int createnew = query(u, v) + 1;
        int extend = (pos[v] == -1 ? 0 : query(u, pos[v]) + cntpaths[v] + 1);
        if (upd) {
            if (createnew >= extend) {
                pos[u] = u, cntpaths[u] = 1;
            }
            
            else {
                pos[u] = pos[v], cntpaths[u] = cntpaths[v] + 1;
            }
        }
        
        return max(createnew, extend);
    };
    
    int sz = edges[u].size();
    for (int i = 0; i < sz; i++) {
        int res = 0, d = 0;
        auto [v, w] = edges[u][i];
        if (dep[v] < dep[w]) {
            swap(v, w);
            d ^= 1;
        }
        
        // dbgm(u, v, w, i, dep[v], dep[w]);
        if (u != w) continue;
        dp[u] = max(dp[u], findbest(u, v, d, true));
    }
    
    for (int i = 0; i < sz; i++) {
        auto [v, w] = edges[u][i];
        bool flag = false, flag2 = false;
        int lca = getlca(v, w), res = 0;
        flag |= (lca == v || lca == w);
        if (i != 0) {
            auto [vv, ww] = edges[u][i - 1];
            if (ww == u && ww == v) flag2 = true, v = vv;
        }
        
        if (!flag || flag2) {
            int l = findbest(u, v), r = findbest(u, w);
            // dbgm(u, v, w, i, l, r, flag, flag2);
            dp[u] = max(dp[u], l + r - (flag2 ? 0 : 1) - query(u, u));
        }
    }
    
    dp[u] = max(dp[u], x);
    update(u, -dp[u]);
}

void solve() {
    cin >> n >> qq;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    memset(pos, -1, sizeof(pos));
    dfs(0);
    precomp();
    // dbg(tin2);
    // dbg(tout2);
    while (qq--) {
        int sz;
        cin >> sz;
        if (sz == 0) {
            cout << "0\n";
            continue;    
        }
        
        vector<pi> nodes(sz);
        vector<int> a(sz), sorted;
        for (int i = 0; i < sz; i++) {
            cin >> a[i];
            a[i]--;
            nodes[i] = {tin[a[i]], a[i]};
        }
        
        sort(nodes.begin(), nodes.end());
        stack<int> stk;
        vector<int> used(1, 0);
        stk.push(0);
        for (int i = 0; i < sz; i++) {
            auto [temp, u] = nodes[i];
            if (u == 0) continue;
            used.push_back(u);
            while (stk.size() > 1) {
                int v = stk.top();
                if (getlca(v, u) == v) break;
                stk.pop();
                int vv = stk.top();
                int lca = getlca(v, u);
                if (dep[vv] <= dep[lca]) {
                    if (lca != vv) {
                        stk.push(lca);
                        used.push_back(lca);
                    }
                    
                    adjvir[lca].push_back(v);
                    break;
                }
                
                adjvir[vv].push_back(v);
            }
            
            stk.push(u);
        }
        
        while (stk.size() > 1) {
            int v = stk.top();
            stk.pop();
            int vv = stk.top();
            adjvir[vv].push_back(v);
        }
        
        for (int i = 0; i < sz; i++) {
            update(a[i], 1);    
        }
        
        for (int i = 1; i < sz; i++) {
            if (query(a[i - 1], a[i]) == 2) {
                int lca = getlca(a[i - 1], a[i]);
                edges[lca].push_back({a[i - 1], a[i]});
            }
        }
        
        b.reset();
        dfs2(0);
        // dbg(dp);
        // dbg(edges);
        // dbg(pos);
        // dbg(cntpaths);
        cout << sz - 1 - dp[0] << "\n";
        b.reset();
        for (int u : used) {
            adjvir[u].clear();
            edges[u].clear();
            dp[u] = 0, pos[u] = -1, cntpaths[u] = 0;
        }
    }
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 30660kb

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: 0
Accepted
time: 3ms
memory: 29312kb

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
0
0
1
4
3
5

result:

ok 7 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 30392kb

input:

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

output:

0
0
3
2
0
1
0
1
0
1

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 3ms
memory: 30544kb

input:

1 1
1 1

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 3ms
memory: 31312kb

input:

1 0

output:


result:

ok 0 number(s): ""

Test #6:

score: 0
Accepted
time: 1ms
memory: 30716kb

input:

20 15
9 4
3 9
10 9
7 14
2 1
16 13
15 20
6 1
8 11
18 19
20 3
12 7
9 17
7 13
8 5
19 20
10 12
1 8
9 8
3 8 12 15
2 5 4
6 17 4 8 7 5 18
1 7
1 18
2 2 20
5 13 6 5 15 17
1 6
1 9
7 4 15 3 2 9 5 13
2 16 18
2 2 6
2 5 17
8 1 11 8 12 9 18 13 17
7 5 6 13 1 11 18 9

output:

1
0
4
0
0
0
2
0
0
4
0
0
0
4
4

result:

ok 15 numbers

Test #7:

score: 0
Accepted
time: 1ms
memory: 26760kb

input:

20 15
15 2
4 12
6 3
20 16
7 15
6 14
13 10
11 20
3 9
13 4
5 19
1 14
5 7
18 9
18 8
17 12
8 2
11 19
17 1
2 3 11
5 9 11 14 20 3
4 9 11 13 4
6 18 6 5 16 7 17
2 2 14
1 11
2 9 3
1 10
2 17 8
1 8
1 16
6 13 17 10 2 4 3
7 2 3 7 6 15 9 17
3 14 3 10
7 9 19 4 2 20 8 11

output:

0
3
1
3
0
0
0
0
0
0
0
5
6
1
6

result:

ok 15 numbers

Test #8:

score: 0
Accepted
time: 2ms
memory: 30396kb

input:

20 15
9 5
5 7
5 13
5 10
5 19
17 5
5 2
5 3
16 5
5 11
5 1
8 5
5 18
15 5
5 20
4 5
5 12
5 6
14 5
3 4 13 7
3 8 6 5
1 12
4 3 19 20 6
8 14 7 19 17 18 12 13 11
5 13 15 10 2 1
2 10 4
1 18
1 2
1 6
9 7 18 9 8 16 3 1 10 14
2 2 15
2 2 20
7 4 13 15 7 3 9 14
1 19

output:

1
1
0
2
6
3
0
0
0
0
7
0
0
5
0

result:

ok 15 numbers

Test #9:

score: -100
Wrong Answer
time: 4ms
memory: 30732kb

input:

1000 500
685 415
28 527
771 396
201 538
604 162
631 66
144 596
788 378
919 59
737 550
471 413
3 590
891 52
886 705
350 238
164 224
554 358
909 150
354 441
310 756
380 661
380 867
601 318
197 204
993 673
118 624
249 539
841 737
742 853
250 566
543 663
981 243
60 120
976 801
750 2
694 8
935 831
381 48...

output:

0
3
0
3
4
2
2
0
2
0
4
0
1
4
5
2
0
12
0
14
3
3
5
3
0
0
2
0
4
9
5
5
1
0
40
12
0
18
4
1
1
6
0
7
3
0
0
14
5
1
3
8
5
0
4
0
5
7
2
5
6
0
5
0
1
2
7
3
0
0
6
0
1
8
4
1
11
0
1
0
8
3
2
0
1
2
0
3
9
5
13
2
0
4
2
0
4
1
14
1
4
4
4
0
1
1
10
2
2
0
0
4
10
2
3
10
4
0
13
6
0
19
3
4
9
2
10
6
1
0
0
3
0
0
5
12
5
2
2
1
9
15...

result:

wrong answer 135th numbers differ - expected: '6', found: '5'