Submission #34496

#TimeUsernameProblemLanguageResultExecution timeMemory
34496mohammad_kilaniPipes (CEOI15_pipes)C++14
30 / 100
4673 ms14712 KiB
#include <bits/stdc++.h> using namespace std; #define mod 1000007 #define oo 2000000000 const int N = 100010 , LOGN = 18; bitset< N > bridge; int dp[LOGN][N] , prnt[N] , num[N] , cur[N] , depth[N]; vector< pair<int,int> > t[N]; int find(int a){ return (a == prnt[a] ? a : prnt[a] = find(prnt[a])); } int DFS(int node,int prnt){ int sum = 0 , s = 0; for(int i=0;i<t[node].size();i++){ if(t[node][i].first == prnt) continue; s = DFS(t[node][i].first,node); if(s > 0) bridge[t[node][i].second] = false; sum += s; } sum+= cur[node]; cur[node] = 0 ; return sum; } void DFS2(int node,int pr,int pr2,int d){ dp[0][node] = pr; depth[node] = d; for(int j=1;(1 << j) <= num[pr2];j++){ if(dp[j-1][node] == -1) dp[j][node] = -1; else dp[j][node] = dp[j-1][dp[j-1][node]]; } prnt[node] = pr2; for(int i=0;i<t[node].size();i++){ if(t[node][i].first == pr) continue; DFS2(t[node][i].first,node,pr2,d+1); } } int lca(int u,int v){ if(depth[u] > depth[v]) swap(u,v); for(int i=LOGN-1;i>=0;i--){ if(depth[u] + (1 << i) <= depth[v]) v = dp[i][v] ; } if(u == v) return u; for(int i=LOGN-1;i>=0;i--){ if(dp[i][u] != dp[i][v]){ u = dp[i][u]; v = dp[i][v]; } } return dp[0][u]; } int main() { //freopen("in.txt","r",stdin); int n , m , cnt = 0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ prnt[i] = i; dp[0][i] = -1; num[i] = 1; } int u , v; for(int i=0;i<m;i++){ scanf("%d%d",&u,&v); int a= find(u); int b= find(v); if(a == b){ cur[v]++; cur[u]++; cur[lca(u,v)]-=2; } else{ bridge[cnt] = true; t[u].push_back(make_pair(v,cnt)); t[v].push_back(make_pair(u,cnt++)); if(num[a] > num[b]){ DFS(v,u); DFS2(v,u,a,depth[u] + 1); num[a] += num[b]; num[b] = 0 ; } else{ DFS(u,v); DFS2(u,v,b,depth[v] + 1); num[b] += num[a]; num[a] = 0 ; } } } for(int i=1;i<=n;i++){ if(prnt[i] == i){ DFS(i,-1); } } for(int i=1;i<=n;i++){ for(int j=0;j<t[i].size();j++){ if(i > t[i][j].first) continue; if(bridge[t[i][j].second]){ printf("%d %d\n",i,t[i][j].first); } } } return 0; }

Compilation message (stderr)

pipes.cpp: In function 'int DFS(int, int)':
pipes.cpp:16:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<t[node].size();i++){
              ~^~~~~~~~~~~~~~~
pipes.cpp: In function 'void DFS2(int, int, int, int)':
pipes.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<t[node].size();i++){
              ~^~~~~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:101:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<t[i].size();j++){
               ~^~~~~~~~~~~~
pipes.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
pipes.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~
#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...