QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#116176 | #4814. Exciting Travel | HaccerKat | WA | 4ms | 31312kb | C++20 | 10.2kb | 2023-06-28 11:23:25 | 2023-06-28 11:23:28 |
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], 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'