oj.uz

Submission #154723

# Submission time Handle Problem Language Result Execution time Memory
154723 2019-09-24T07:58:25 Z nicolaalexandra Pipes (CEOI15_pipes) C++17
90 / 100
 5000 ms 13060 KB 
#include <iostream>
#include <vector>
#define DIM 100002
using namespace std;
int t[DIM],t2[DIM],low[DIM],niv[DIM];
vector <int> L[DIM];
int n,m,i,j,x,y,idx;
inline int get_rad (int x){
    int nr = x;
    while (t[x] > 0)
        x = t[x];
    while (t[nr] > 0){
        int aux = t[nr];
        t[nr] = x;
        nr = aux;
    }
    return x;
}
inline int get_rad2 (int x){
    int nr = x;
    while (t2[x] > 0)
        x = t2[x];
    while (t2[nr] > 0){
        int aux = t2[nr];
        t2[nr] = x;
        nr = aux;
    }
    return x;
}
void dfs(int nod, int tata){
    niv[nod] = low[nod] = ++idx;
    for(int i=0;i<L[nod].size();++i){
        int vecin = L[nod][i];
        if (vecin == tata)
            continue;
        if (niv[vecin])
            low[nod] = min (low[nod],niv[vecin]);
        else {
            dfs (vecin, nod);
            low[nod] = min (low[nod],low[vecin]);
            if (low[vecin] > niv[nod] && get_rad2(nod) != get_rad2(vecin))
                cout<<nod<<" "<<vecin<<"\n";
        }}}

int main (){

    cin>>n>>m;
    for (i=1;i<=n;++i)
        t[i] = t2[i] = -1;

    for (i=1;i<=m;++i){
        cin>>x>>y;
        int rx = get_rad (x), ry = get_rad (y);
        if (rx != ry){
            L[x].push_back(y);
            L[y].push_back(x);
            if (t[rx] < t[ry]){
                t[rx] += t[ry];
                t[ry] = rx;
            } else {
                t[ry] += t[rx];
                t[rx] = ry;
            }
        } else {
            /// nodurile se alfa deja in aceeasi multime si toate muchiile
            /// de pe drumul de la x la y NU pot fi critice
            /// oare merge daca fac din nou paduri pt nodurile astea?
            int rx2 = get_rad2 (x), ry2 = get_rad2 (y);
            if (rx2 != ry2){
                L[x].push_back(y); /// astea ar fi muchiile de intoarcere pt biconexe
                L[y].push_back(x);
                if (t2[rx2] < t2[ry2]){
                    t2[rx2] += t2[ry2];
                    t2[ry2] = rx2;
                } else {
                    t2[ry2] += t2[rx2];
                    t2[rx2] = ry2;
                }}}}
    for (i=1;i<=n;++i)
        if (!niv[i])
            dfs (i,0);


    return 0;
}

Compilation message

pipes.cpp: In function 'void dfs(int, int)':
pipes.cpp:32:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<L[nod].size();++i){
                 ~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3192 KB Output is correct
2 Correct 17 ms 2936 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 3020 KB Output is correct
2 Correct 492 ms 2888 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 886 ms 3700 KB Output is correct
2 Correct 1035 ms 3296 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1443 ms 5148 KB Output is correct
2 Correct 1269 ms 4956 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1926 ms 9928 KB Output is correct
2 Correct 1646 ms 7164 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2991 ms 11064 KB Output is correct
2 Correct 2981 ms 8716 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3974 ms 13060 KB Output is correct
2 Correct 3790 ms 8916 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4964 ms 13004 KB Output is correct
2 Correct 4663 ms 8920 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5069 ms 7244 KB Time limit exceeded
2 Halted 0 ms 0 KB -