# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
143134 | Ruxandra985 | Pipes (CEOI15_pipes) | C++14 | 1692 ms | 65536 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |