# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
208246 | alexandra_udristoiu | Pipes (CEOI15_pipes) | C++14 | 2241 ms | 7800 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<iostream>
#include<vector>
#include<cstdio>
#define DIM 100005
using namespace std;
int n, m, i, x, y, r1, r2, nr;
int r[DIM], t[DIM], nxt[DIM], niv[DIM];
char ok[DIM];
vector<int> v[DIM];
int rad(int x){
while(r[x] > 0){
x = r[x];
}
return x;
}
int urm(int x){
int y, aux;
y = nxt[x];
while(ok[y] == 1){
y = nxt[y];
}
while(x != y){
aux = nxt[x];
nxt[x] = y;
x = aux;
}
return y;
}
void dfs(int nod, int tt){
niv[nod] = 1 + niv[tt];
for(int i = 0; i < v[nod].size(); i++){
if(v[nod][i] != tt){
dfs(v[nod][i], nod);
}
}
if(t[nod] != tt){
ok[ t[nod] ] = ok[nod];
t[nod] = tt;
nxt[nod] = t[nod];
}
}
int main(){
scanf("%d%d", &n, &m);
for(i = 1; i <= n; i++){
r[i] = -1;
}
for(; m; m--){
scanf("%d%d", &x, &y);
r1 = rad(x);
r2 = rad(y);
if(r1 != r2){
/*nr++;
if(nr == n){
break;
}*/
v[x].push_back(y);
v[y].push_back(x);
if(r[r1] < r[r2]){
r[r1] += r[r2];
r[r2] = r1;
dfs(y, x);
ok[y] = 0;
}
else{
r[r2] += r[r1];
r[r1] = r2;
dfs(x, y);
ok[x] = 0;
}
}
else{
while(x != y){
if(niv[x] > niv[y]){
ok[x] = 1;
x = urm(x);
}
else{
ok[y] = 1;
y = urm(y);
}
}
}
}
for(i = 1; i <= n; i++){
if(ok[i] == 0 && t[i] != 0){
cout<< i <<" "<< t[i] <<"\n";
}
}
}
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... |