QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #462734 | #6888. Teyvat | Fortitude | AC ✓ | 2022ms | 240116kb | C++23 | 7.1kb | 2024-07-04 01:39:40 | 2024-07-04 01:39:43 |
Judging History
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);
vector <bool> gd(2 * n + 1);
for (int i = 1; i <= n; ++i) {
if (is_cut[i]) {
int x = id[i];
gd[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 (!gd[a[0]]) { // it's not cut
cout << n << '\n';
}
else {
if (glob == 1176)
cout << "shock ";
cout << ret[a[0]] << '\n';
}
continue;
}
if (sz(a) == 2) {
if (!gd[a[0]] && !gd[a[1]]) {
cout << "1\n";
continue;
}
if (!gd[a[0]]) {
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 (!gd[a[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 (!gd[a[i]]) {
ok = 1;
break;
}
}
if (ok) {
cout << "0\n";
continue;
}
if (!gd[a[0]] && !gd[a[u]]) {
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 (!gd[a[0]])
cout << sz[a[u]] << '\n';
else if (!gd[a[u]])
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 (!gd[a[i]]) {
ok = 1;
break;
}
}
if (ok) {
cout << "0\n";
continue;
}
if (glob == 1176)
cout << "i am tired ";
if (!gd[a[u]] && !gd[a[v]])
cout << "1\n";
else if (!gd[a[u]])
cout << sz[a[v]] << '\n';
else if (!gd[a[v]])
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2022ms
memory: 240116kb
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 ...
output:
144 91 92 91 615 91 92 92 91 92 91 90 92 91 270 182 18 32 1 18 1 17 17 3 17 1 1 0 18 18 18 3 1 3 18 48 18 6 1 1 34 32 1 18 4 18 18 3 18 18 18 18 34 18 1 34 1 1 18 18 1 32 2 2 18 6 1 3 3 1 18 18 34 18 32 34 34 15 15 15 15 15 15 15 15 15 2 2 15 28 1 15 15 15 15 15 28 15 2 15 2 15 15 28 15 1 15 1 2 0 1...
result:
ok 693539 lines