| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 454661 |
2021-08-05T07:05:18 Z |
AmirrezaM |
Pipes (CEOI15_pipes) |
C++17 |
|
1505 ms |
49256 KB |
// ki bood ke goft Ghatinga?
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<pii,int> ppiii;
// vectors and Sets:
#define vc vector
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rend(), (c).rbegin
// pairs
#define mp make_pair
#define fr first
#define sc second
// loops
#define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
#define ROF(i , n , m) for(int (i) = (n) ; (i) >= (m) ; (i)--)
//#define FOR(n) for(int (i) = (o) ; (i) < (n) ; (i)++)
//#define ROF(n) for(int (i) = (m) ; (i) >= (0) ; (i)--)
// execution time check and Debug
#define StartEX; clock_t startExeTime = clock();
#define EndEX; clock_t endExeTime = clock();
#define ExTime; cerr << "\nTotal Execution Time is: " << double(-double(startExeTime)+double(endExeTime)) / CLOCKS_PER_SEC;
#define debug(x) cerr << #x << " : " << x << '\n'
#define endl "\n"
// time optimization
#define Heh ios::sync_with_stdio(false);cin.tie(0);
#pragma GCC optimize("Ofast")
//#pragma GCC option("tune=native") // f*ck
//#pragma GCC target("avx,avx2,fma")
// useful functions
#define BPT(n) (1 << floor(log2((n))));
#define LPT(n) (1 << ceil(log2((n))*1.0));
//Calculates b'th power of a
ll pw(ll a,ll b){
ll ret = 1;
ll mul = a;
while(b > 0){
if(b&1)
ret = (ret * mul);
mul = (mul * mul);
b /= 2;
}
return ret;
}
//Converts s string to int
ll to_int(string s){
ll ret = 0;
FOR(i,0,s.size()){
ret += pw(10,s.size()-i-1) * (ll)(s[i] - '0');
}
return ret;
}
const int MAXN = 1e5 + 15;
int n , m , par[2][MAXN] , rnk[2][MAXN] , mark[MAXN] , tin[MAXN] , tme;
vc<int> adj[MAXN];
int get(int v , int t){return par[t][v] = (par[t][v] == v ? v : get(par[t][v] , t));}
bool uni(int a , int b , int t){
a = get(a , t) , b = get(b , t);
if(a == b) return 0;
if(rnk[t][a] < rnk[t][b]) swap(a , b);
par[t][b] = a;
rnk[t][a] += (rnk[t][a] == rnk[t][b]);
return 1;
}
int dfs(int v , int p = -1){
mark[v] = 1;
tin[v] = tme++;
int low = MAXN;
bool fl = 0;
for(int u : adj[v]){
if(mark[u] == 0) low = min(low , dfs(u , v));
if(mark[u] == 1){
if(u == p){
if(fl) low = min(low , tin[u]);
else fl = 1;
}
else low = min(low , tin[u]);
}
}
mark[v] = 2;
if(low >= tin[v] and p != -1){
cout << v+1 << " " << p+1 << endl;
}
return low;
}
int main()
{
int ed = 0;
Heh;
cin >> n >> m;
iota(par[0] , par[0] + n , 0);
iota(par[1] , par[1] + n , 0);
for(int i = 0 ; i < m ; i++){
int s , e;
cin >> s >> e;
s-- , e--;
if(uni(s , e , 0) || uni(s , e , 1)) adj[s].pb(e) , adj[e].pb(s) , ed++;
}
assert(ed <= 2*MAXN);
for(int v = 0 ; v < n ; v++){
if(!mark[v]) dfs(v);
}
}
// ki seda kard Patinga?
Compilation message
pipes.cpp:31:9: warning: ISO C++11 requires whitespace after the macro name
31 | #define StartEX; clock_t startExeTime = clock();
| ^~~~~~~
pipes.cpp:32:9: warning: ISO C++11 requires whitespace after the macro name
32 | #define EndEX; clock_t endExeTime = clock();
| ^~~~~
pipes.cpp:33:9: warning: ISO C++11 requires whitespace after the macro name
33 | #define ExTime; cerr << "\nTotal Execution Time is: " << double(-double(startExeTime)+double(endExeTime)) / CLOCKS_PER_SEC;
| ^~~~~~
pipes.cpp: In function 'll to_int(std::string)':
pipes.cpp:25:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
25 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
| ^
pipes.cpp:61:5: note: in expansion of macro 'FOR'
61 | FOR(i,0,s.size()){
| ^~~
pipes.cpp:25:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
| ~~~~^~~~~
pipes.cpp:61:5: note: in expansion of macro 'FOR'
61 | FOR(i,0,s.size()){
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
3148 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2932 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
121 ms |
3004 KB |
Output is correct |
| 2 |
Correct |
121 ms |
2884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
237 ms |
3720 KB |
Output is correct |
| 2 |
Correct |
246 ms |
3320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
392 ms |
5532 KB |
Output is correct |
| 2 |
Runtime error |
296 ms |
18972 KB |
Memory limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
489 ms |
11056 KB |
Output is correct |
| 2 |
Runtime error |
442 ms |
25752 KB |
Memory limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
754 ms |
12416 KB |
Output is correct |
| 2 |
Runtime error |
789 ms |
23520 KB |
Memory limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1028 ms |
14740 KB |
Output is correct |
| 2 |
Runtime error |
1010 ms |
28164 KB |
Memory limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1213 ms |
14620 KB |
Output is correct |
| 2 |
Runtime error |
1237 ms |
34148 KB |
Memory limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1505 ms |
14084 KB |
Output is correct |
| 2 |
Runtime error |
1433 ms |
49256 KB |
Memory limit exceeded |
