Submission #46464

#TimeUsernameProblemLanguageResultExecution timeMemory
46464sorry_BenqPipes (CEOI15_pipes)C++17
20 / 100
1549 ms26548 KiB
/** * Sources: various */ #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; typedef long long ll; typedef vector<int> vi; typedef pair<int, int> pii; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define FOR(i, a, b) for (int i=a; i<(b); i++) #define F0R(i, a) for (int i=0; i<(a); i++) #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--) #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--) #define sz(x) (int)(x).size() #define mp make_pair #define pb push_back #define f first #define s second #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() const int MOD = 1000000007; template<typename T> ostream& operator<< (ostream& out, const pair<T, T>& v) { out << "{" << v.first << ", " << v.second << "}"; return out; } template<typename T> ostream& operator<< (ostream& out, const vector<T>& v) { out << "["; size_t last = v.size() - 1; for(size_t i = 0; i < v.size(); ++i) { out << v[i]; if (i != last) out << ", "; } out << "]"; return out; } template<typename T> ostream& operator<< (ostream& out, const set<T>& v) { out << "["; auto pen = v.end(); pen--; for (auto it = v.begin(); it != v.end(); it++){ out << *it; if (it != pen){ out << ", "; } } out << "]"; return out; } template<typename T> ostream& operator<< (ostream& out, const Tree<T>& v) { out << "["; auto pen = v.end(); pen--; for (auto it = v.begin(); it != v.end(); it++){ out << *it; if (it != pen){ out << ", "; } } out << "]"; return out; } template<int SZ> struct DSU { int par[SZ]; DSU() { F0R(i,SZ) par[i] = i; } int get(int x) { // path compression if (par[x] != x) par[x] = get(par[x]); return par[x]; } bool unite(int x, int y) { // union-by-rank x = get(x), y = get(y); if (x == y) return 0; par[y] = x; return 1; } }; DSU<100005> one_connected; DSU<100005> two_connected; vector<int> adj[100005]; int timer = 1; int ti[100005]; int fup[100005]; bool vis[100005]; map<pii, int> cnt; void DFS(int v, int p = -1){ if (vis[v]) return; vis[v] = true; ti[v] = fup[v] = timer++; //cout << v << ' ' << timer << endl; for (int j: adj[v]){ if (j == p) continue; if (vis[j]){ fup[v] = min(ti[j], fup[v]); } else{ DFS(j, v); fup[v] = min(fup[j], fup[v]); if (fup[j] > ti[v]){ if (v < j) swap(v, j); if (cnt[make_pair(v, j)] == 1){ cout << v << ' ' << j << endl; } } } } } int main() { ios_base::sync_with_stdio(0);cin.tie(0); int n, m; cin >> n >> m; int u, v; for (int i = 1; i <= n; i++){ ti[i] = -1; fup[i] = -1; } for (int i = 0; i < m; i++){ cin >> u >> v; if (!one_connected.unite(u, v)){ if (!two_connected.unite(u, v)){ continue; } else{ adj[u].pb(v); adj[v].pb(u); if (u < v) swap(u, v); cnt[make_pair(u, v)]++; } } else{ adj[u].pb(v); adj[v].pb(u); if (u < v) swap(u, v); cnt[make_pair(u, v)]++; } } for (int i = 1; i <= n; i++){ if (!vis[i]){ DFS(i); } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...