Submission #669380

#TimeUsernameProblemLanguageResultExecution timeMemory
669380ShaShiPipes (CEOI15_pipes)C++17
70 / 100
979 ms18940 KiB
#include <bits/stdc++.h> #define lint long long int #define dint long double #define ll long long #define endl "\n" #define pii pair<int, int> #define pb push_back #define F first #define S second using namespace std; const int MOD = (int)1e9 + 23; const int MAXN = (int)2e5 + 23; const int MAX_LOG = 17 + 1; const int INF = (int)1e9 + 23; int n, m, tmp, tmp2, u, v; int par1[MAXN], par2[MAXN], sz1[MAXN], sz2[MAXN], h[MAXN], dp[MAXN], seen[MAXN], googool[MAXN], p[MAXN]; vector<pii> adj[MAXN]; int get_par1(int v) { return (par1[v] == -1? v : par1[v] = get_par1(par1[v])); } int get_par2(int v) { return (par2[v] == -1? v : par2[v] = get_par2(par2[v])); } bool merge1(int u, int v) { u = get_par1(u); v = get_par1(v); if (u == v) return 0; par1[u] = v; return 1; } bool merge2(int u, int v) { u = get_par2(u); v = get_par2(v); if (u == v) return 0; par2[u] = v; return 1; } void DFS(int v) { seen[v] = 1; for(auto w:adj[v]) { int u = w.F; int ind=w.S; if(seen[u]){ if(googool[ind] == 0 && h[u] < (h[v])){ dp[v]++; dp[u]--; } continue; } h[u] = h[v] + 1; p[u] = v; googool[ind] = 1; DFS(u); dp[v] += dp[u]; } } int32_t main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; fill(par1, par1+n+1, -1); fill(par2, par2+n+1, -1); tmp = 1; for (int i=1; i<=m; i++) { cin >> u >> v; if (merge1(u, v)) { adj[u].pb({v, tmp}); adj[v].pb({u, tmp}); tmp++; } else if (merge2(u, v)) { adj[u].pb({v, tmp}); adj[v].pb({u, tmp}); tmp++; } } for (int i=1; i<=n; i++) { if (!seen[i]) { DFS(i); } } for (int i=1; i<=n ; i++) { if (!dp[i] && p[i]) { cout << p[i] << " " << i << endl; } } 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...