QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #340749 | #995. 桥 | iorit# | WA | 81ms | 19644kb | C++14 | 1.2kb | 2024-02-29 11:43:29 | 2024-02-29 11:43:30 |
Judging History
answer
#include <bits/stdc++.h>
#define LL long long
#define sl(n) strlen(n)
#define endline puts("")
#define pii pair<int , int>
#define pr_q priority_queue
#define debug puts("DEBUG.")
using namespace std;
const int N = 5e5 + 10;
const int inf = ~0u >> 2;
int n,m;
struct edge
{
int v,w,nxt;
}e[N << 1];
int hd[N],cnt = 1;
void add(int u , int v)
{
++cnt,e[cnt].v = v;
e[cnt].nxt = hd[u],hd[u] = cnt;
}
vector<int> vc;
int dfn[N],dfn_t,low[N];
bool vis[N];
void dfs(int u)
{
// cout << u << endl;
dfn[u] = low[u] = ++dfn_t;
for(int i = hd[u];i;i = e[i].nxt)
{
if(vis[i] )
continue;
int v = e[i].v;
if(dfn[v] )
low[u] = min(low[u] , dfn[v] );
else
{
vis[i] = vis[i ^ 1] = 1;
dfs(v);
low[u] = min(low[u] , low[v] );
if( low[v] == dfn[v] )
vc.push_back(i / 2 * 2);
}
}
// cout << u << " low= " << low[u] << " dfn= " << dfn[u] << endl;
}
int main()
{
cin >> n >> m;
for(int i = 1,u,v;i <= m;i++)
{
scanf("%d%d" , &u , &v);
if(u == v)
continue;
add(u , v),add(v , u);
}
dfs(1);
sort( vc.begin() , vc.end() );
for(int id : vc)
printf("%d %d\n" , e[id ^ 1].v , e[id].v);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 79ms
memory: 15656kb
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: 9ms
memory: 6812kb
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: 0
Accepted
time: 18ms
memory: 10108kb
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 20915 38008 17235 41266 10868 19902 3480 40329 42530 19516 26641 43027 24643 2098 41076 6838 38205 33280 34270 29027 35410 20866 26447 35052 27397 33860 1309 35388 534 25757 13594 30628 31979 38444 33887 39751 20313 28554 31809 39630 34623 43195 34069 16150 42137 13811 35147 3120 17275 36681 29...
result:
ok 719 lines
Test #4:
score: 0
Accepted
time: 81ms
memory: 17720kb
input:
49992 399165 8308 37286 41253 33600 18414 44236 38678 30403 43606 1459 28337 38324 36285 9669 49565 49785 14096 21520 15003 30556 38808 7647 33458 31201 44773 8348 33753 49802 32310 3168 21074 25490 4402 33409 24426 43322 14935 32620 23905 18122 42387 34044 20819 31052 6164 2735 35280 40824 41926 37...
output:
result:
ok 0 lines
Test #5:
score: -100
Wrong Answer
time: 63ms
memory: 19644kb
input:
93887 364115 62725 36008 22626 20572 53515 88946 64267 92727 59627 27874 53335 47736 10090 1365 48040 77604 18170 17458 33510 65809 87370 77875 32271 41379 64896 22693 4152 51548 36587 78683 79022 6239 84531 74481 49359 48362 69495 53641 65507 39043 499 64326 21156 26621 53001 49045 42104 20835 4044...
output:
61751 86972 42227 69851 18546 67197 53527 76954 87658 22664 62803 2140 69814 55962 33513 56374 31638 20537 34381 29291 68374 8989 28705 82997 37853 11838 85649 44706 8509 91134 18296 11378 92358 75974 5241 45589 84385 70583 49370 41829 56528 7447 78468 3397 24604 73865 53348 50063 33370 75315 38611 ...
result:
wrong answer 1st lines differ - expected: '42227 69851', found: '61751 86972'