QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#116181#4814. Exciting TravelHaccerKatWA 10ms31520kbC++2010.2kb2023-06-28 11:26:072023-06-28 11:26:09

Judging History

This is the latest submission verdict.

  • [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:26:09]
  • Judged
  • Verdict: WA
  • Time: 10ms
  • Memory: 31520kb
  • [2023-06-28 11:26:07]
  • Submitted

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 && v == u && getlca(vv, w) == u) 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: 1ms
memory: 30460kb

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: 1ms
memory: 28652kb

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: 4ms
memory: 30492kb

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: 1ms
memory: 30288kb

input:

1 1
1 1

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 0ms
memory: 28668kb

input:

1 0

output:


result:

ok 0 number(s): ""

Test #6:

score: 0
Accepted
time: 0ms
memory: 30256kb

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: 7ms
memory: 30328kb

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: 4ms
memory: 28640kb

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: 0
Accepted
time: 1ms
memory: 31300kb

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
6
12
5
2
2
1
9
15...

result:

ok 500 numbers

Test #10:

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

input:

1000 500
657 521
621 14
522 258
78 524
221 712
607 614
270 378
307 865
702 869
336 541
649 488
606 807
272 312
152 213
931 861
442 227
3 298
700 757
74 634
829 765
670 748
532 283
398 90
626 913
610 879
340 850
183 369
326 877
872 809
684 303
574 161
798 339
803 842
182 571
585 732
262 859
851 515
7...

output:

0
1
9
0
7
3
0
0
1
6
0
0
1
7
13
17
10
6
4
1
1
6
2
0
2
2
0
6
0
3
0
9
14
1
7
4
1
1
17
12
1
4
4
5
1
5
0
1
2
8
5
7
3
0
3
0
0
17
11
6
13
0
2
5
8
5
0
3
0
7
5
0
0
2
0
1
1
1
6
10
2
3
2
10
1
0
16
1
4
0
28
0
1
0
6
0
2
0
0
0
2
1
4
1
6
6
1
0
6
1
0
5
0
0
1
4
0
3
0
1
12
2
2
7
0
5
0
0
5
2
5
0
0
0
2
0
0
1
9
4
0
1
9
...

result:

ok 500 numbers

Test #11:

score: 0
Accepted
time: 4ms
memory: 28728kb

input:

1000 500
642 460
642 15
642 123
415 642
642 302
402 642
596 642
139 642
449 642
715 642
642 377
642 622
718 642
642 172
262 642
240 642
642 872
256 642
642 403
642 486
227 642
642 708
642 907
113 642
642 400
829 642
642 430
142 642
765 642
219 642
470 642
744 642
642 871
30 642
642 282
422 642
623 6...

output:

0
0
1
0
2
0
9
1
0
0
3
16
5
11
0
3
1
7
2
4
5
0
2
1
0
8
1
27
1
2
2
2
8
1
5
0
2
13
1
1
3
8
7
7
23
9
3
1
10
2
1
4
0
7
0
2
2
2
0
5
1
4
15
3
4
0
3
0
6
0
0
0
0
0
1
0
4
1
1
1
0
9
6
1
8
1
8
0
0
5
6
3
0
8
2
4
13
15
6
2
10
0
1
19
2
11
0
4
0
6
10
0
0
6
2
7
2
0
21
11
0
3
2
8
0
4
0
0
0
8
0
1
7
8
0
1
0
0
8
20
3
0
...

result:

ok 500 numbers

Test #12:

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

input:

1000 500
268 91
243 255
301 436
34 358
177 16
819 174
305 923
256 126
803 359
603 677
302 485
801 546
79 963
873 946
163 496
893 771
521 23
820 389
344 700
442 824
16 222
166 820
364 678
853 173
389 917
36 303
987 560
388 284
191 904
268 629
193 572
956 945
783 520
899 763
514 245
991 477
937 239
64...

output:

1
0
2
7
1
0
16
0
15
5
0
12
0
9
0
2
1
12
0
0
5
2
48
0
10
0
2
1
0
10
0
0
0
0
6
11
0
8
6
10
0
3
0
11
2
1
0
8
2
17
13
0
8
22
0
3
0
4
4
0
3
4
3
11
3
11
0
0
1
7
0
31
17
0
2
5
0
8
1
1
1
0
0
5
2
1
2
3
8
2
0
3
5
14
1
0
2
6
3
0
5
0
5
1
0
1
0
0
9
4
0
0
1
6
0
0
0
3
0
0
1
4
2
0
23
3
10
1
3
2
1
2
0
1
11
5
0
0
2
1...

result:

wrong answer 23rd numbers differ - expected: '49', found: '48'