QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#588125 | #995. 桥 | shiqiaqiaya | WA | 76ms | 21516kb | C++17 | 3.2kb | 2024-09-25 02:07:29 | 2024-09-25 02:07:29 |
Judging History
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());
}
Details
Tip: Click on the bar to expand more detailed information
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'