QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#116154 | #4814. Exciting Travel | HaccerKat | WA | 3ms | 32288kb | C++20 | 10.4kb | 2023-06-28 11:04:53 | 2023-06-28 11:04:56 |
Judging History
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], 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: 32288kb
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: 32220kb
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
Wrong Answer
time: 1ms
memory: 30428kb
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 0
result:
wrong answer 10th numbers differ - expected: '1', found: '0'