Submission #437675

#TimeUsernameProblemLanguageResultExecution timeMemory
437675xiaowuc1Pipes (CEOI15_pipes)C++17
90 / 100
1525 ms22188 KiB
#include <algorithm> #include <array> #include <bitset> #include <cassert> #include <chrono> #include <cstring> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <random> #include <set> #include <stack> #include <vector> using namespace std; // BEGIN NO SAD #define rep(i, a, b) for(int i = a; i < (b); ++i) #define trav(a, x) for(auto& a : x) #define all(x) x.begin(), x.end() #define sz(x) (int)(x).size() #define mp make_pair #define pb push_back #define eb emplace_back #define lb lower_bound #define ub upper_bound typedef vector<int> vi; #define f first #define s second // END NO SAD typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<vector<ll>> matrix; int find(vector<int>& p, int x) { return p[x] == x ? x : (p[x] = find(p, p[x])); } bool merge(vector<int>& p, int x, int y) { x = find(p, x); y = find(p, y); if(x == y) return false; p[x] = y; return true; } bool visited[100005]; vector<int> edges[100005]; int aptime = 1; int discTime[100005]; int low[100005]; int parv[100005]; void dfsForAP(int curr, int parent) { visited[curr] = true; int numchild = 0; discTime[curr] = low[curr] = ++aptime; sort(all(edges[curr])); for(int i = 0; i < sz(edges[curr]); ) { int out = edges[curr][i]; bool dup = i+1 < sz(edges[curr]) && edges[curr][i] == edges[curr][i+1]; if(!visited[out]) { numchild++; parv[out] = curr; dfsForAP(out, curr); low[curr] = min(low[curr], low[out]); if(!dup && low[out] > discTime[curr]) { cout << curr << " " << out << "\n"; } } else if(out != parv[curr]) { low[curr] = min(low[curr], discTime[out]); } if(dup) i += 2; else i++; } } void solve() { int n, m; cin >> n >> m; { vector<int> p1(n+1); vector<int> p2(n+1); iota(all(p1), 0); iota(all(p2), 0); while(m--) { int a, b; cin >> a >> b; if(merge(p1, a, b)) { edges[a].pb(b); edges[b].pb(a); } else if(merge(p2, a, b)) { edges[a].pb(b); edges[b].pb(a); } } } for(int i = 1; i <= n; i++) { if(visited[i]) continue; dfsForAP(i, -1); } } // what would chika do // are there edge cases (N=1?) // are array sizes proper (scaled by proper constant, for example 2* for koosaga tree) // integer overflow? // DS reset properly between test cases // are you doing geometry in floating points int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); solve(); }
#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...