Submission #143142

#TimeUsernameProblemLanguageResultExecution timeMemory
143142Ruxandra985Pipes (CEOI15_pipes)C++14
50 / 100
1732 ms22908 KiB
#include <cstdio> #include <vector> #include <algorithm> #define DIMN 100005 using namespace std; int fth[DIMN],fth2[DIMN],sum[DIMN]; vector <int> v[DIMN]; int eul[2*DIMN],nv[2*DIMN],first[DIMN]; bool f[DIMN]; int d[18][2*DIMN]; int logg[2*DIMN]; int elem; int root (int nod){ int init = nod,aux; while (fth[nod]>0){ nod = fth[nod]; } while (fth[init]>0){ /// amortizare aux = fth[init]; fth[init] = nod; init = aux; } return nod; } int root2 (int nod){ int init = nod,aux; while (fth2[nod]>0){ nod = fth2[nod]; } while (fth2[init]>0){ /// amortizare aux = fth2[init]; fth2[init] = nod; init = aux; } return nod; } void dfs (int nod,int tata){ int i,vecin; f[nod] = 1; for (i=0;i<v[nod].size();i++){ vecin = v[nod][i]; if (vecin!=tata){ dfs(vecin , nod); sum[nod]+=sum[vecin]; if (!sum[vecin]){ printf ("%d %d\n",nod,vecin); } } } } void dfs_lca (int nod,int niv,int tt){ int i,vecin; eul[++elem]=nod; nv[elem] = niv; first[nod] = elem; /// prima poz; for (i=0;i<v[nod].size();i++){ vecin=v[nod][i]; if (vecin!=tt){ dfs_lca(vecin,niv+1,nod); eul[++elem]=nod; nv[elem]=niv; } } } int query (int x,int y){ int px,py,len; px=first[x]; py=first[y]; /// minimul din intervalul px py /// in d e pozitia din eul unde e nivelul minim if (px>py) swap(px,py); len = py-px+1; if (nv[ d[logg[len]][px] ] < nv[ d[logg[len]][py-(1<<logg[len])+1] ]) return d[logg[len]][px]; return d[logg[len]][py-(1<<logg[len])+1]; } int main() { //freopen ("a.in" , "r" , stdin); int n,m,i,x,y,rx,ry; scanf ("%d%d",&n,&m); for (i=1;i<=n;i++) fth[i] = fth2[i] = -1; for (i=1;i<=m;i++){ scanf ("%d%d",&x,&y); rx = root(x); ry = root(y); if (rx != ry){ /// sunt in cc diferite v[x].push_back(y); v[y].push_back(x); /// mai multi arbori if (fth[rx] < fth[ry]){ fth[rx]+=fth[ry]; fth[ry] = rx; } else { fth[ry]+=fth[rx]; fth[rx] = ry; } } else { rx = root2(x); ry = root2(y); if (rx!=ry){ /// unesti in fth2 if (fth2[rx] < fth2[ry]){ fth2[rx]+=fth2[ry]; fth2[ry] = rx; } else { fth2[ry]+=fth2[rx]; fth2[rx] = ry; } } } } /// faci lca din arborele v for (i=1;i<=n;i++){ if (!first[i]) dfs_lca (i,0,0); } for (i=2;i<=2*n;i++) logg[i] = logg[i/2] + 1; for (i=1;i<=elem;i++){ d[0][i] = i; } for (int powe=1;powe<=logg[elem];powe++){ for (i=1;i + (1<<powe)-1 <=elem;i++){ if (nv[d[powe-1][i]] < nv[d[powe-1][i + (1<<(powe-1))]]) d[powe][i] = d[powe-1][i]; else d[powe][i] = d[powe-1][i + (1<<(powe-1))]; } } for (i=1;i<=n;i++){ /// daca ai o muchie in fth2 , stergi din fth if (fth2[i]>0){ int lca = eul[query (i , fth2[i])]; sum[i]++; sum[fth2[i]]++; sum[lca]-=2; } } for (i=1;i<=n;i++){ if (!f[i]) dfs(i,0); } return 0; }

Compilation message (stderr)

pipes.cpp: In function 'void dfs(int, int)':
pipes.cpp:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
pipes.cpp: In function 'void dfs_lca(int, int, int)':
pipes.cpp:56:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:82:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d%d",&n,&m);
     ~~~~~~^~~~~~~~~~~~~~
pipes.cpp:86:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d%d",&x,&y);
         ~~~~~~^~~~~~~~~~~~~~
#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...