| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 527434 |
2022-02-17T11:49:34 Z |
zaneyu |
Pipes (CEOI15_pipes) |
C++14 |
|
379 ms |
14672 KB |
/*input
10 12
1 7
1 8
1 6
2 8
6 7
5 8
2 5
2 3
2 4
3 4
10 9
10 9
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;
#define ld double
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
const ll maxn=1e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
ll mult(ll a,ll b){
return ((a%MOD)*(b%MOD))%MOD;
}
ll mypow(ll a,ll b){
if(b<=0) return 1;
ll res=1LL;
while(b){
if(b&1) res=mult(res,a);
a=mult(a,a);
b>>=1;
}
return res;
}
/** Interface */
inline int readChar();
template <class T = int> inline T readInt();
template <class T> inline void writeInt( T x, char end = 0 );
inline void writeChar( int x );
inline void writeWord( const char *s );
/** Read */
static const int buf_size = 4096;
inline int getChar() {
static char buf[buf_size];
static int len = 0, pos = 0;
if (pos == len)
pos = 0, len = fread(buf, 1, buf_size, stdin);
if (pos == len)
return -1;
return buf[pos++];
}
inline int readChar() {
int c = getChar();
while (c <= 32)
c = getChar();
return c;
}
template <class T>
inline T readInt() {
int s = 1, c = readChar();
T x = 0;
if (c == '-')
s = -1, c = getChar();
while ('0' <= c && c <= '9')
x = x * 10 + c - '0', c = getChar();
return s == 1 ? x : -x;
}
/** Write */
static int write_pos = 0;
static char write_buf[buf_size];
inline void writeChar( int x ) {
if (write_pos == buf_size)
fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
write_buf[write_pos++] = x;
}
template <class T>
inline void writeInt( T x, char end ) {
if (x < 0)
writeChar('-'), x = -x;
char s[24];
int n = 0;
while (x || !n)
s[n++] = '0' + x % 10, x /= 10;
while (n--)
writeChar(s[n]);
if (end)
writeChar(end);
}
inline void writeWord( const char *s ) {
while (*s)
writeChar(*s++);
}
struct Flusher {
~Flusher() {
if (write_pos)
fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
}
} flusher;
struct ufds{
int par[maxn];
void init(int n){
REP(i,n) par[i]=i;
}
inline int find(int u){
if(par[u]==u) return u;
return par[u]=find(par[u]);
}
inline void merge(int a,int b){
a=find(a),b=find(b);
par[a]=b;
}
}u1,u2;
int low[maxn],depth[maxn];
vector<int> v[maxn];
int cur=0;
inline void dfs(int u,int p){
low[u]=depth[u]=++cur;
bool hv=0;
for(auto x:v[u]){
if(x==p and !hv){
hv=1;
continue;
}
if(!depth[x]){
dfs(x,u);
MNTO(low[u],low[x]);
if(low[x]>depth[u]){
cout<<u+1<<' '<<x+1<<'\n';
}
//check AP low[x]>=depth[u],bridge >
//doesnt work for multiedges
}
else{
low[u]=min(low[u],depth[x]);
}
}
}
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int n=readInt(),m=readInt();
vector<pii> ed;
u1.init(n),u2.init(n);
REP(i,m){
int a=readInt(),b=readInt();
--a,--b;
if(u1.find(a)!=u1.find(b)){
u1.merge(a,b);
v[a].pb(b);
v[b].pb(a);
}
else if(u2.find(a)!=u2.find(b)){
u2.merge(a,b);
v[a].pb(b);
v[b].pb(a);
}
}
REP(i,n){
if(!depth[i]) dfs(i,-1);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3072 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
6184 KB |
Output is correct |
| 2 |
Correct |
35 ms |
6208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
6616 KB |
Output is correct |
| 2 |
Correct |
62 ms |
8104 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
106 ms |
10228 KB |
Output is correct |
| 2 |
Correct |
82 ms |
9376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
140 ms |
10140 KB |
Output is correct |
| 2 |
Correct |
118 ms |
7836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
196 ms |
11468 KB |
Output is correct |
| 2 |
Correct |
150 ms |
9296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
289 ms |
13228 KB |
Output is correct |
| 2 |
Correct |
258 ms |
10480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
312 ms |
14672 KB |
Output is correct |
| 2 |
Correct |
286 ms |
10560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
379 ms |
13424 KB |
Output is correct |
| 2 |
Correct |
335 ms |
13664 KB |
Output is correct |
