QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#116153#4814. Exciting TravelHaccerKatRE 1ms3444kbC++2010.4kb2023-06-28 11:04:362023-06-28 11:04:37

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:04:37]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3444kb
  • [2023-06-28 11:04:36]
  • 提交

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 = 8;
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], par[N], pos[N], dir[N], cntpaths[N];
void dfs2(int u) {
    int x = 0;
    for (int v : adjvir[u]) {
        par[v] = 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, dir[u] = d, cntpaths[u] = 1;
            }
            
            else {
                pos[u] = pos[v], dir[u] = d, 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 || (dir[v] != d && dir[v] != -1)) 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 == 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(par, -1, sizeof(par));
    memset(pos, -1, sizeof(pos));
    memset(dir, -1, sizeof(dir));
    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, par[u] = -1, pos[u] = -1, dir[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: 3428kb

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: 3444kb

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: -100
Runtime Error

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:


result: