Submission #143134

#TimeUsernameProblemLanguageResultExecution timeMemory
143134Ruxandra985Pipes (CEOI15_pipes)C++14
0 / 100
1692 ms65536 KiB
#include <cstdio> #include <vector> #include <set> #include <deque> #include <algorithm> #include <map> #define DIMN 100005 using namespace std; int fth[DIMN],fth2[DIMN],f[DIMN]; vector <int> v[DIMN]; 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 ers (int nod){ int aux; if (fth[nod] < 0){ /// nod e fix radacina int a = 0 , b = 0; for (int i=0;i<v[nod].size();i++){ int vecin = v[nod][i]; if (fth[vecin] == nod){ if (!a){ a = vecin; fth[a] = -1; /// in fond , nu conteaza asa de mult acum } else{ fth[vecin] = a; v[a].push_back(vecin); break; } } } fth[nod] = -1; return; } while (fth[nod]>0){ aux = fth[nod]; fth[nod] = -1; nod = aux; } } int main() { // freopen ("a.in" , "r" , stdin); // freopen ("a.out" , "w" , stdout); 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 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; } } } } for (i=1;i<=n;i++){ if (fth[i] > 0){ v[fth[i]].push_back(i); } } for (i=1;i<=n;i++){ /// daca ai o muchie in fth2 , stergi din fth if (fth2[i]>0){ x = i; y = fth2[i]; /// stergi x ... root si y ... root din fth if (!f[x]) ers(x); if (!f[y]) ers(y); f[x] = f[y] = 1; } } for (i=1;i<=n;i++){ if (fth[i]>0) printf ("%d %d\n" , i , fth[i]); } return 0; }

Compilation message (stderr)

pipes.cpp: In function 'void ers(int)':
pipes.cpp:39:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<v[nod].size();i++){
                      ~^~~~~~~~~~~~~~
pipes.cpp:38:21: warning: unused variable 'b' [-Wunused-variable]
         int a = 0 , b = 0;
                     ^
pipes.cpp: In function 'int main()':
pipes.cpp:67: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:71: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...