QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #462726 | #6888. Teyvat | Fortitude | RE | 0ms | 0kb | C++23 | 7.3kb | 2024-07-04 01:27:51 | 2024-07-04 01:27:57 |
answer
#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define f first
#define s second
using namespace std;
using ll = long long;
using pii = pair <int, int>;
const int N = 1e6 + 5;
int n, _n, m, q, tin[N], tout[N], fup[N], id[N], up[N][20], sz[N], cnt[N];
bool is_cut[N];
vector <int> g[N];
stack <int> stk;
vector <vector <int> > comps;
void dfs(int v, int p = 0) {
tin[v] = fup[v] = ++tin[0];
stk.push(v);
for (auto to : g[v]) {
if (to == p)
continue;
if (tin[to])
fup[v] = min(fup[v], tin[to]);
else {
dfs(to, v);
fup[v] = min(fup[v], fup[to]);
if (fup[to] >= tin[v]) {
is_cut[v] = (tin[v] > 1 || tin[to] > 2);
comps.pb({v});
while (comps.back().back() != to) {
comps.back().pb(stk.top());
stk.pop();
}
}
}
}
}
void calc(int v, int p = 0) {
tin[v] = ++tin[0];
up[v][0] = p;
for (int i = 1; i < 20; ++i)
up[v][i] = up[up[v][i - 1]][i - 1];
sz[v] = cnt[v];
for (auto to : g[v]) {
if (to != p) {
calc(to, v);
sz[v] += sz[to];
}
}
tout[v] = ++tin[0];
}
bool upper(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v) {
if (upper(u, v))
return u;
if (upper(v, u))
return v;
for (int i = 19; i >= 0; i--) {
if (up[u][i] && !upper(up[u][i], v))
u = up[u][i];
}
return up[u][0];
}
int glob;
void solve() {
cin >> n >> m >> q;
comps.clear();
tin[0] = _n = 0;
for (int i = 1; i <= n; ++i) {
g[i].clear();
tin[i] = fup[i] = is_cut[i] = id[i] = 0;
}
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
dfs(1);
for (int i = 1; i <= 2 * n; ++i) {
g[i].clear();
cnt[i] = sz[i] = 0;
for (int j = 0; j < 20; ++j)
up[i][j] = 0;
}
// building the block-cut tree
for (int i = 1; i <= n; ++i) {
if (is_cut[i]) {
id[i] = ++_n;
cnt[_n] = 1;
}
}
for (auto comp : comps) {
int v = ++_n;
for (auto x : comp) {
if (!is_cut[x]) {
id[x] = v;
++cnt[v];
} else {
g[id[x]].pb(v);
g[v].pb(id[x]);
}
}
}
tin[0] = 0;
calc(1);
vector <ll> ret(2 * n + 1);
for (int i = 1; i <= n; ++i) {
if (is_cut[i])
assert(cnt[id[i]] == 1);
else
assert(cnt[id[i]] != 1);
}
for (int x = 1; x <= 2 * n; ++x) {
if (cnt[x] == 1) {
int sum = n - sz[x] + 1;
ret[x] = n - sz[x] + 1;
for (auto to : g[x]) {
if (upper(x, to)) {
ret[x] += sz[to] * 1ll * sum;
sum += sz[to];
}
}
}
}
while (q--) {
int k;
cin >> k;
vector <int> a;
map <int, int> mp;
for (int i = 0; i < k; ++i) {
int x;
cin >> x;
a.pb(id[x]);
}
++glob;
if (sz(a) == 1) {
if (cnt[a[0]] > 1) { // it's not cut
cout << n << '\n';
}
else {
if (glob == 1176)
cout << "shock ";
cout << ret[a[0]] << '\n';
}
continue;
}
if (sz(a) == 2) {
if (cnt[a[0]] != 1 && cnt[a[1]] != 1) {
cout << "1\n";
continue;
}
if (cnt[a[0]] != 1) {
if (!upper(a[1], a[0]))
cout << sz[a[1]] << '\n';
else {
int par = a[0];
for (int i = 19; i >= 0; i--) {
if (up[par][i] && !upper(up[par][i], a[1]))
par = up[par][i];
}
cout << n - sz[par] << '\n';
}
continue;
}
if (cnt[a[1]] != 1) {
if (!upper(a[0], a[1]))
cout << sz[a[0]] << '\n';
else {
int par = a[1];
for (int i = 19; i >= 0; i--) {
if (up[par][i] && !upper(up[par][i], a[0]))
par = up[par][i];
}
cout << n - sz[par] << '\n';
}
continue;
}
}
sort(all(a), [&] (int x, int y) {
return tin[x] < tin[y];
});
int l = 0;
while (l + 1 < sz(a) && upper(a[l], a[l + 1]))
++l;
int u = l;
if (u == sz(a) - 1) {
if (glob == 1176)
cout << "no bugs ";
bool ok = 0;
for (int i = 1; i < sz(a) - 1; ++i) {
if (cnt[a[i]] > 1) {
ok = 1;
break;
}
}
if (ok) {
cout << "0\n";
continue;
}
if (cnt[a[0]] > 1 && cnt[u] > 1) {
cout << "1\n";
continue;
}
int par = a[u];
for (int i = 19; i >= 0; i--) {
if (up[par][i] && !upper(up[par][i], a[0]))
par = up[par][i];
}
if (cnt[a[0]] > 1)
cout << sz[a[u]] << '\n';
else if (cnt[a[u]] > 1)
cout << n - sz[par] << '\n';
else
cout << sz[a[u]] * 1ll * (n - sz[par]) << '\n';
continue;
}
++l;
bool bad = 0;
if (upper(a[0], a[l])) {
if (lca(a[1], a[l]) != a[0])
bad = 1;
}
if (bad) {
cout << "0\n";
continue;
}
while (l + 1 < sz(a) && upper(a[l], a[l + 1]))
++l;
int v = l;
if (v < sz(a) - 1) { // not forming a path
cout << "0\n";
continue;
}
bool ok = 0;
for (int i = 0; i < sz(a); ++i) {
if (i == u || i == v)
continue;
if (cnt[a[i]] > 1) {
ok = 1;
break;
}
}
if (ok) {
cout << "0\n";
continue;
}
if (glob == 1176)
cout << "i am tired ";
if (cnt[a[u]] > 1 && cnt[a[v]] > 1)
cout << "1\n";
else if (cnt[a[u]] > 1)
cout << sz[a[v]] << '\n';
else if (cnt[a[v]] > 1)
cout << sz[a[u]] << '\n';
else
cout << sz[a[u]] * 1ll * sz[a[v]] << '\n';
}
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
cnt[0] = 10001;
int T;
cin >> T;
while (T--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
1000 92 95 16 76 55 19 12 57 7 39 90 38 89 48 60 29 67 35 52 32 83 10 80 64 11 66 63 90 57 17 70 20 42 31 87 91 41 33 72 12 14 9 38 30 82 72 21 9 81 40 9 73 60 71 82 48 69 70 26 72 34 25 62 10 75 83 92 16 18 34 79 15 72 65 13 64 12 37 63 46 16 32 1 23 78 22 18 78 68 49 78 48 13 39 72 39 44 27 25 20 ...