| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 146643 |
2019-08-24T19:19:46 Z |
12tqian |
Pipes (CEOI15_pipes) |
C++14 |
|
3012 ms |
65540 KB |
#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
const double PI = 4 * atan(1);
#define sz(x) (int)(x).size()
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define vi vector<int>
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define vpi vector<pair<int, int>>
#define vpd vector<pair<double, double>>
#define pd pair<double, double>
#define f0r(i,a) for(int i=0;i<a;i++)
#define f1r(i,a,b) for(int i=a;i<b;i++)
#define trav(a, x) for (auto& a : x)
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
void fast_io(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
}
void io(string taskname){
string fin = taskname + ".in";
string fout = taskname + ".out";
const char* FIN = fin.c_str();
const char* FOUT = fout.c_str();
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
fast_io();
}
template<int SZ> struct BCC {
int N;
vector<int> adj[SZ];
vector<vector<pair<int, int>>> fin;
void addEdge(int u, int v) {
adj[u].push_back(v), adj[v].push_back(u);
}
int ti = 0, disc[SZ], low[SZ], comp[SZ], par[SZ];
vector<pair<int, int>> st;
void BCCutil(int u, bool root = 0) {
disc[u] = low[u] = ti++;
int child = 0;
for (int i: adj[u]) {
if (i != par[u]){
if (disc[i] == -1) {
child ++; par[i] = u;
st.push_back({u,i});
BCCutil(i);
low[u] = min(low[u],low[i]);
if ((root && child > 1) || (!root && disc[u] <= low[i])) { // articulation point!
vector<pair<int, int>> tmp;
while (st.back() != make_pair(u,i)) tmp.push_back(st.back()), st.pop_back();
tmp.push_back(st.back()), st.pop_back();
fin.push_back(tmp);
}
}
else if (disc[i] < disc[u]) {
low[u] = min(low[u],disc[i]);
st.push_back({u,i});
}
}
}
}
void bcc(int _N) {
N = _N;
for(int i = 1; i< N+1; i++){
par[i] = disc[i] = low[i] = -1;
}
for(int i = 1; i<N+1; i++){
if (disc[i] == -1) {
BCCutil(i,1);
if ((st).size()) fin.push_back(st);
st.clear();
}
}
}
};
const int MAX = 1e5 + 5;
BCC<MAX> bcc;
int main(){
fast_io();
int n, m;
cin >> n >> m;
f0r(i, m){
int ai, bi;
cin >> ai >> bi;
bcc.addEdge(ai, bi);
}
bcc.bcc(n);
f0r(i, sz(bcc.fin)){
if(sz(bcc.fin[i]) == 1){
cout << bcc.fin[i][0].f << " " << bcc.fin[i][0].s << endl;
}
}
return 0;
}
Compilation message
pipes.cpp:1:0: warning: ignoring #pragma comment [-Wunknown-pragmas]
#pragma comment(linker, "/stack:200000000")
pipes.cpp: In function 'void io(std::__cxx11::string)':
pipes.cpp:52:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(FIN, "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:53:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(FOUT, "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2680 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
2680 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
3576 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
3320 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
191 ms |
25812 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
347 ms |
39868 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
660 ms |
64984 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1147 ms |
65536 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1551 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2214 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2742 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3012 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
