Submission #153163

#TimeUsernameProblemLanguageResultExecution timeMemory
153163MercenaryPipes (CEOI15_pipes)C++14
50 / 100
5073 ms46240 KiB
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/trie_policy.hpp> #define pb push_back #define mp make_pair #define taskname "A" using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef pair<int,int> ii; typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; const int maxn = 1e5 + 5; const int logn = log2(maxn) + 1; int n , m , nEdge = 0; struct Edge{ int u , v; bool col; }e[maxn]; int par[maxn] , P[maxn][logn]; int lab[maxn] , h[maxn] , dp[maxn]; vector<int> adj[maxn]; int FindLab(int u){ return lab[u] < 0 ? u : lab[u] = FindLab(lab[u]); } void BuildLCA(int u , int par){ P[u][0] = par; for(int i = 1 ; i < logn && P[u][i - 1] ; ++i){ P[u][i] = P[P[u][i - 1]][i - 1]; } } void dfs(int u , int par){ for(int c : adj[u]){ if(par != e[c].u + e[c].v - u){ h[e[c].u + e[c].v - u] = h[u] + 1; ::par[e[c].u + e[c].v - u] = c; BuildLCA(e[c].u + e[c].v - u , u); dfs(e[c].u + e[c].v - u , u); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); if(fopen(taskname".INP","r")){ freopen(taskname".INP", "r",stdin); freopen(taskname".OUT", "w",stdout); } fill_n(lab,maxn,-1); fill_n(par,maxn,-1); cin >> n >> m; for(int i = 1 ; i <= m ; ++i){ int u , v;cin >> u >> v; int s , t; s = FindLab(u); t = FindLab(v); if(s != t){ e[nEdge].u = u;e[nEdge].v = v; if(lab[s] > lab[t])swap(s , t) , swap(u , v); lab[s] += lab[t]; lab[t] = s; adj[u].pb(nEdge); adj[v].pb(nEdge); ++nEdge; } } for(int i = 1 ; i <= n ; ++i){ if(h[i] == 0){ dfs(i , 0); } } fill_n(lab,maxn,-1); rewind(stdin); cin >> n >> m; for(int i = 1 ; i <= m ; ++i){ int u , v;cin >> u >> v; int s , t; s = FindLab(u); t = FindLab(v); if(s != t){ if(lab[s] > lab[t])swap(s , t) , swap(u , v); lab[s] += lab[t]; lab[t] = s; }else{ auto lca = [&](int u , int v){ if(h[u] < h[v])swap(u , v); for(int i = 0 ; i < logn ; ++i){ if((h[u] - h[v]) & (1 << i))u = P[u][i]; } if(u == v)return u; for(int i = logn - 1 ; i >= 0 ; --i){ if(P[u][i] != P[v][i])u = P[u][i] , v = P[v][i]; } return P[u][0]; }; dp[u]++;dp[v]++; dp[lca(u,v)] -= 2; } } fill_n(h,maxn,0); for(int i = 1 ; i <= n ; ++i){ if(h[i] == 0){ function<void(int,int)> dfs = [&](int u , int par){ for(int c : adj[u]){ int v = e[c].u + e[c].v - u; if(v != par){ h[v] = h[u] + 1; dfs(v , u); dp[u] += dp[v]; } } if(dp[u] > 0)e[::par[u]].col = 1; }; dfs(i , 0); } } for(int i = 0 ; i < nEdge ; ++i){ if(e[i].col == 0)cout << e[i].u << " " << e[i].v << endl; } }

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:57:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
pipes.cpp:58:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...