QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#341864 | #995. 桥 | Ishy# | WA | 6ms | 10132kb | C++14 | 2.6kb | 2024-02-29 22:05:38 | 2024-02-29 22:05:38 |
Judging History
answer
// Sea, You & Me
#include<bits/stdc++.h>
#define LL long long
#define DB double
#define MOD 1000000007
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define lowbit(x) ((-x) & x)
#define MP make_pair
#define MT make_tuple
#define VI vector<int>
#define VL vector<LL>
#define VII VI::iterator
#define VLI VL::iterator
#define all(x) x.begin(), x.end()
#define EB emplace_back
#define PII pair<int, int>
#define PLI pair<LL, int>
#define SI set<int>
#define SII SI::iterator
#define fi first
#define se second
using namespace std;
template<typename T> void chkmn(T &a, const T b) { (a > b) && (a = b); }
template<typename T> void chkmx(T &a, const T b) { (a < b) && (a = b); }
void Inc(int &a, const int &b) { ((a += b) >= MOD) && (a -= MOD); }
void Dec(int &a, const int &b) { ((a -= b) < 0) && (a += MOD); }
void Mul(int &a, const int &b) { a = 1LL * a * b % MOD; }
void Sqr(int &a) { a = 1LL * a * a % MOD; }
int inc(const int &a, const int &b) { return (a + b >= MOD) ? a + b - MOD : a + b; }
int dec(const int &a, const int &b) { return (a - b < 0) ? a - b + MOD : a - b; }
int mul(const int &a, const int &b) { return 1LL * a * b % MOD; }
int sqr(const int &a) { return 1LL * a * a % MOD; }
int qwqmi(int x, int k = MOD - 2)
{
int res = 1;
while(k)
{
if(k & 1) Mul(res, x);
k >>= 1, Sqr(x);
}
return res;
}
template<typename T> void read(T &x)
{
x = 0;
int f = 1;
char ch = getchar();
while(!isdigit(ch))
{
if(ch == '-')
f = -1;
ch = getchar();
}
while(isdigit(ch))
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x = x * f;
}
const int N = 1e5 + 5;
const int M = 5e5 + 5;
int n, m;
PII ed[N];
struct Lexington
{
int e, ne;
};
struct Noshiro
{
int idx = 1, h[N];
Lexington lxt[M << 1];
void clear()
{
idx = 1;
memset(h, 0, sizeof(h));
}
void add(int x, int y)
{
lxt[++idx] = (Lexington){y, h[x]};
h[x] = idx;
}
void adds(int x, int y)
{
add(x, y), add(y, x);
}
}nsr;
int low[N], dfn[N], timestamp;
bool bridge[M];
void tarjan(int u, int from)
{
low[u] = dfn[u] = ++timestamp;
for(int i = nsr.h[u]; i; i = nsr.lxt[i].ne)
{
int v = nsr.lxt[i].e;
if(!dfn[v])
{
tarjan(v, i);
chkmn(low[u], low[v]);
if(dfn[u] < low[v])
bridge[i / 2] = 1;
}
else if(i != (from ^ 1))
chkmn(low[u], dfn[v]);
}
}
int main()
{
read(n), read(m);
for(int i = 1; i <= m; ++i)
{
int x, y;
read(x), read(y);
nsr.adds(x, y);
ed[i] = MP(x, y);
}
for(int i = 1; i <= n; ++i)
if(!dfn[i]) tarjan(i, 0);
for(int i = 1; i <= m; ++i)
if(bridge[i]) printf("%d %d\n", ed[i].fi, ed[i].se);
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 6ms
memory: 10132kb
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:
23086 9796 11649 13969 15710 11305 17825 4536 24043 4070 11329 8017 11641 11818 23345 12685 975 14740 11747 13836 1074 21620 20267 8205 22847 10889 9139 22269
result:
wrong output format Extra information in the output file