QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#462692#6888. TeyvatFortitudeWA 1954ms239852kbC++234.8kb2024-07-04 00:39:112024-07-04 00:39:15

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 00:39:15]
  • 评测
  • 测评结果:WA
  • 用时:1954ms
  • 内存:239852kb
  • [2024-07-04 00:39:11]
  • 提交

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];
}
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] = cnt[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();
    // 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 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]);
        }
        if (sz(a) == 1) {
            if (cnt[a[0]] > 1) { // it's not cut
                cout << n << '\n';
            }
            else
                cout << ret[a[0]] << '\n';
            continue;
        }
        if (sz(a) == 2) {
            if (cnt[a[0]] != 1 || cnt[a[1]] != 1) {
                cout << "1\n";
                continue;
            }
        }
        bool ok = 1;
        for (auto x : a) {
            ok &= (cnt[x] == 1);
        }
        if (!ok) {
            cout << "0\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) {
            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];
            }
            cout << sz[a[u]] * 1ll * (n - sz[par]) << '\n';
            continue;
        }
        ++l;
        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;
        }
        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;
}
/*
simple self-made test doesn't work for two cutting nodes
1
11 14 5
1 2
2 3
3 4
4 1
2 5
5 7
7 6
6 2
2 8
8 9
9 10
8 10
10 11
11 8
2 2 8
2 9 6
4 8 9 10 11
2 2 8
2 2 8
*/

详细

Test #1:

score: 0
Wrong Answer
time: 1954ms
memory: 239852kb

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
1
92
91
270
182
18
32
1
18
1
17
17
1
17
1
1
0
18
18
18
1
1
1
18
48
18
6
1
1
34
32
1
18
4
18
18
1
18
18
18
18
34
18
1
34
1
1
18
18
1
32
1
1
18
6
1
1
1
1
18
18
34
18
32
34
34
15
15
15
15
15
15
15
15
15
1
1
15
28
1
15
15
15
15
15
28
15
1
15
1
15
15
28
15
1
15
1
1
0
15...

result:

wrong answer 12th lines differ - expected: '90', found: '1'