QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #797183 | #6225. 生成树 | propane | 10 | 153ms | 38400kb | C++20 | 3.4kb | 2024-12-02 18:18:11 | 2024-12-02 18:18:13 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cassert>
using namespace std;
using LL = long long;
struct Edge{
int to;
int id;
operator int() const { return to; }
};
struct LowLink{
int n;
vector<vector<Edge> > g;
vector<int> in, out, low;
int ts;
// map<int, int> bridge;
LowLink(const vector<vector<Edge> > &g) : n(int(g.size()) - 1), g(g) {
ts = 0;
in.assign(n + 1, 0);
out.assign(n + 1, 0);
low.assign(n + 1, 0);
for(int i = 1; i <= n; i++){
if (in[i] == 0){
tarjan(i, -1);
}
}
id.assign(n + 1, 0);
cnt = 0;
for(int i = 1; i <= n; i++){
if (id[i] == 0){
dfs(i, -1);
}
}
group.resize(cnt + 1);;
for(int i = 1; i <= n; i++){
group[id[i]].push_back(i);
}
}
void tarjan(int u, int from){
in[u] = low[u] = ++ts;
for(auto j : g[u]){
if (!in[j]){
tarjan(j, j.id);
low[u] = min(low[u], low[j]);
// if (low[j] > in[u]){
// bridge[j.id] = j;
// }
}
else if (j.id != from) low[u] = min(low[u], in[j]);
}
out[u] = ts;
}
int cnt;
vector<vector<int> > group;
vector<int> id;
void dfs(int u, int fa){
if (fa != -1 && low[u] <= in[fa]){
id[u] = id[fa];
}
else{
id[u] = ++cnt;
}
for(auto j : g[u]){
if (id[j] == 0){
dfs(j, u);
}
}
}
};
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n, m;
cin >> n >> m;
vector<vector<Edge> > g(n + 1);
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
g[a].push_back({b, i});
g[b].push_back({a, i});
}
LowLink lk(g);
vector<int> d(n + 1);
for(int i = 1; i <= n; i++){
for(auto [j, _] : g[i]){
if (lk.id[i] == lk.id[j]){
d[j] += 1;
}
}
}
const int mod = 998244353;
int ans = 1;
for(int i = 1; i <= lk.cnt; i++){
auto &v = lk.group[i];
vector<int> p;
for(auto x : v){
if (d[x] == 3){
p.push_back(x);
}
}
if (p.empty())
ans = (LL)v.size() * ans % mod;
else{
assert(p.size() == 2);
vector<int> d(n + 1, -1);
queue<int> q;
d[p[0]] = 0;
q.push(p[0]);
while(!q.empty()){
int t = q.front();
q.pop();
for(auto [j, id] : g[t]){
if (minmax(t, j) == minmax(p[0], p[1])) continue;
if (d[j] == -1){
d[j] = d[t] + 1;
q.push(j);
}
}
}
int t = (v.size() + d[p[1]] * LL(v.size() - d[p[1]])) % mod;
ans = 1LL * ans * t % mod;
}
}
cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1ms
memory: 3924kb
input:
1828 1828 277 1778 1778 1650 1650 1169 1778 1812 1169 1041 1650 662 662 1187 662 939 1041 224 224 1098 1169 497 1169 1443 224 1356 1169 719 662 781 1169 818 1041 514 1778 986 939 1721 818 1102 1098 1376 719 1028 818 1084 1812 79 1187 722 719 67 79 1816 1721 695 514 1458 781 696 79 656 224 159 1169 6...
output:
8
result:
ok single line: '8'
Test #2:
score: 10
Accepted
time: 1ms
memory: 3896kb
input:
1816 1816 123 240 123 1242 123 1055 240 521 1242 927 521 590 1055 1257 240 514 927 848 1257 603 590 1631 848 1419 1419 1502 603 1761 514 447 1502 609 603 313 313 1322 1631 1482 447 1361 609 1375 447 1624 1624 845 1322 9 1361 1290 1375 737 1624 1813 1290 1752 1290 586 586 933 933 1223 9 1144 1144 17 ...
output:
111
result:
ok single line: '111'
Subtask #2:
score: 0
Wrong Answer
Test #3:
score: 0
Wrong Answer
time: 14ms
memory: 12368kb
input:
48897 49999 44175 43993 44175 13021 13021 23273 13021 35214 44175 43686 23273 25433 25433 46383 43686 45608 13021 26466 46383 13484 23273 28961 43686 21379 25433 46792 45608 16454 44175 3160 13484 16479 46792 39917 3160 11777 39917 30437 26466 19880 39917 29973 43686 43378 26466 40225 23273 38230 30...
output:
117545887
result:
wrong answer 1st lines differ - expected: '778245294', found: '117545887'
Subtask #3:
score: 0
Wrong Answer
Test #5:
score: 0
Wrong Answer
time: 44ms
memory: 21400kb
input:
96912 99999 71789 3940 71789 21169 21169 50408 50408 68720 68720 67449 50408 69195 69195 64168 64168 70336 69195 81723 3940 91136 21169 75782 50408 36767 71789 77653 50408 30673 30673 79224 70336 4586 77653 32309 91136 57060 36767 3517 71789 16769 75782 11348 68720 46490 64168 15995 36767 51887 5040...
output:
339406458
result:
wrong answer 1st lines differ - expected: '373712628', found: '339406458'
Subtask #4:
score: 0
Wrong Answer
Test #8:
score: 0
Wrong Answer
time: 35ms
memory: 19944kb
input:
92616 99999 70768 12420 70768 67024 70768 37650 67024 14933 12420 81054 81054 6944 70768 9552 14933 31629 70768 51744 81054 62067 31629 49539 51744 47773 9552 19607 81054 89603 6944 2797 81054 78691 70768 39322 37650 16268 31629 34316 78691 18322 70768 46861 70768 36460 9552 42042 51744 53292 53292 ...
output:
832908844
result:
wrong answer 1st lines differ - expected: '810112214', found: '832908844'
Subtask #5:
score: 0
Wrong Answer
Test #10:
score: 0
Wrong Answer
time: 41ms
memory: 19816kb
input:
91653 99999 1786 58358 1786 87672 1786 62883 1786 56997 56997 79414 87672 56317 56997 30068 58358 43013 1786 25272 56317 11600 11600 57554 25272 37668 87672 30501 79414 1591 1591 74 30501 74650 57554 83362 87672 25595 1786 19541 25272 68790 30068 59157 19541 56546 79414 59557 79414 32173 56317 63887...
output:
932843952
result:
wrong answer 1st lines differ - expected: '396960248', found: '932843952'
Subtask #6:
score: 0
Runtime Error
Test #12:
score: 0
Runtime Error
input:
98982 100000 37308 3159 37308 76920 37308 67591 67591 78501 76920 30922 67591 90524 3159 70630 67591 82536 70630 85743 70630 73885 85743 51097 82536 81427 70630 75802 82536 11006 75802 11893 82536 94161 75802 66471 51097 19126 19126 4071 75802 90741 75802 8924 66471 9660 8924 50226 50226 13970 50226...
output:
result:
Subtask #7:
score: 0
Runtime Error
Test #14:
score: 0
Runtime Error
input:
99170 100000 58553 14320 14320 9444 58553 22219 14320 77126 22219 32808 58553 62144 58553 72681 72681 72235 77126 74762 72681 95464 72235 70259 95464 18298 70259 63380 18298 88666 72235 65028 70259 26344 70259 39126 65028 38489 70259 54083 26344 28793 63380 82981 88666 94908 54083 15140 94908 21117 ...
output:
result:
Subtask #8:
score: 0
Runtime Error
Test #16:
score: 0
Runtime Error
input:
148738 150000 97229 147704 147704 3732 3732 126210 147704 114875 97229 4145 114875 125662 126210 54609 126210 125530 125662 57240 3732 12701 114875 148509 125530 127724 57240 36638 54609 145259 125530 16588 16588 82269 148509 110113 12701 83842 145259 86308 36638 91488 110113 18954 86308 4751 18954 ...
output:
result:
Subtask #9:
score: 0
Wrong Answer
Test #18:
score: 0
Wrong Answer
time: 148ms
memory: 35312kb
input:
183279 200000 46233 1718 1718 145581 1718 99335 145581 149635 46233 44778 1718 7931 99335 14807 149635 86473 7931 50719 86473 86707 7931 138797 14807 106593 106593 28 86707 89350 106593 163773 106593 55983 89350 110272 89350 4686 4686 71136 110272 27450 110272 135707 71136 163719 110272 173695 71136...
output:
401024568
result:
wrong answer 1st lines differ - expected: '329641010', found: '401024568'
Subtask #10:
score: 0
Wrong Answer
Test #20:
score: 0
Wrong Answer
time: 153ms
memory: 38400kb
input:
193116 200000 94070 92162 92162 141789 141789 191032 94070 86611 141789 146661 141789 85085 94070 15000 85085 186121 146661 64671 85085 25108 186121 152468 15000 87079 87079 29491 64671 156412 29491 192599 64671 162723 25108 10551 87079 172614 172614 122064 162723 96437 96437 61867 156412 4076 61867...
output:
608176354
result:
wrong answer 1st lines differ - expected: '163752784', found: '608176354'