QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#588125#995. 桥shiqiaqiayaWA 76ms21516kbC++173.2kb2024-09-25 02:07:292024-09-25 02:07:29

Judging History

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

  • [2024-09-25 02:07:29]
  • 评测
  • 测评结果:WA
  • 用时:76ms
  • 内存:21516kb
  • [2024-09-25 02:07:29]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define int long long
using ll = long long;
mt19937_64 rd(time(0));
template <class K, class C = less<>> using paring_heap = __gnu_pbds::priority_queue<K, C>;
template <class K, class V = null_type, class C = less<>> using rb_tree = tree<K, V, C, rb_tree_tag, tree_order_statistics_node_update>;
template <class T, class ... A> void debug(const T & t, const A & ... a) { cerr << "[" << t, ((cerr << ", " << a), ...), cerr << "]\n"; }
const ll mod = [](bool n) { return n ? 998244353 : 1e9 + 7; } (1);

template <ll mod = mod> ll binpow(ll a, ll b, ll res = 1) {
    for (a %= mod; b; b >>= 1, (a *= a) %= mod) {
        if (b & 1) (res *= a) %= mod;
    }
    return res;
}

vector<signed> inv, fact, invfa;
auto INIT_FACT = ([](int n) {
    inv = fact = invfa = vector<signed>(n + 1, 1);
    for (int i = 2; i <= n; i++) {
        fact[i] = (ll)fact[i - 1] * i % mod, invfa[i] = (ll)invfa[i - 1] * (inv[i] = (mod - mod / i) * inv[mod % i] % mod);
    }
} (0), true);
ll C(int n, int m) { return min(n - m, m) < 0 ? 0 : (ll)fact[n] * invfa[m] % mod * invfa[n - m] % mod; }
ll P(int n, int m) { return min(n - m, m) < 0 ? 0 : (ll)fact[n] * invfa[n - m] % mod; }
ll LC(ll n, ll m) { return !m ? 1 : C(n % mod, m % mod) * LC(n / mod, m / mod) % mod; }

template <class type = int, int len = 2> struct Tarjan_UnDir : vector<vector<signed>> {
    vector<array<type, len + 1>> e;  // {u, v, is_bridge}
    vector<signed> dfn, dcc, low;
    vector dc = {};
    Tarjan_UnDir(int n, int m) : vector(n), e(m), dfn(n), dcc(n), low(n) {}
    void operator()(stack<int> s = {}, int tot_dfn = 0) {   // !! 会包含 0 , 可能 0 会成孤岛
        for (int rt = 0; rt < size(); rt++, s = {}) {
            auto self = [&](auto && self, int u, int from) -> void {    // 用 from 而不用 fa 因为可能重边
                s.emplace(u), dfn[u] = low[u] = ++tot_dfn;
                for (auto & i : at(u)) {
                    int v = e[i][0] ^ e[i][1] ^ u;
                    if (!dfn[v]) {
                        self(self, v, i), low[u] = min(low[u], low[v]);
                        if (low[v] > dfn[u]) e[i].back() = true;
                    } else if (i != from) low[u] = min(low[u], dfn[v]);
                }
                if (dfn[u] == low[u]) for (dc.emplace_back(); !dc.back().size() || dc.back().back() != u; ) {
                    dcc[s.top()] = dc.size() - 1, dc.back().emplace_back(s.top()), s.pop();
                }
            };
            self(self, rt, -1);
        }
    }
};

void QAQ() {
    int n, m;
    cin >> n >> m;
    Tarjan_UnDir adj(n + 1, m);

    for (int i = 0, u, v; i < m; i++) {
        cin >> u >> v;
        adj[u].push_back(i), adj[v].push_back(i);
        adj.e[i] = {u, v};
    }

    adj();

    for (auto & [u, v, bri] : adj.e) {
        if (bri) cout << u << " " << v;
    }
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    for (cout << fixed << setprecision(12); t--; QAQ());
}

詳細信息

Test #1:

score: 100
Accepted
time: 76ms
memory: 21516kb

input:

24942 387166
12556 21443
22404 16376
11073 24296
1535 11968
23745 2818
5073 12731
22550 14761
24118 12008
22695 18979
15118 13639
2080 8721
692 22578
22581 15267
9278 4127
7457 21674
17693 23448
10949 23429
9700 6009
14140 5064
7742 15164
17336 1662
18903 9760
17645 19575
6540 11942
11 4937
15282 10...

output:


result:

ok 0 lines

Test #2:

score: 0
Accepted
time: 16ms
memory: 8356kb

input:

10599 87159
4698 4000
60 4705
1476 5947
7273 1716
8004 3018
10094 1717
3092 3493
2613 9681
5427 3723
2510 6343
10113 6322
9257 634
4996 10197
9918 5582
6348 9561
10536 9777
8133 540
1917 7838
6666 2220
7951 815
2873 977
9397 4991
3529 1395
1426 3874
6379 9098
9504 3437
9076 9134
4321 3879
10252 9390...

output:


result:

ok 0 lines

Test #3:

score: -100
Wrong Answer
time: 35ms
memory: 13832kb

input:

43236 126833
40500 20695
21481 27642
28098 41772
412 7750
5862 39561
21777 22303
7868 21217
31658 34299
18532 10934
21931 31023
42926 15624
40332 18017
12484 8663
21927 7910
12504 17943
4379 10252
3523 21794
18641 1965
18633 25061
14639 10800
35958 1441
35044 20249
31491 38161
5749 4468
13403 8413
3...

output:

1349 2091538008 1723541266 1086819902 348040329 4253019516 2664143027 246432098 410766838 3820533280 3427029027 3541020866 2644735052 2739733860 130935388 53425757 1359430628 3197938444 3388739751 2031328554 3180939630 3462343195 3406916150 4213713811 351473120 1727536681 2945432 417599284 127411242...

result:

wrong answer 1st lines differ - expected: '1349 20915', found: '1349 2091538008 1723541266 108...6368 3449038722 117095694 20147'