oj.uz

Submission #54371

# Submission time Handle Problem Language Result Execution time Memory
54371 2018-07-03T09:20:44 Z Costin Andrei Oncescu(#1303) Pipes (CEOI15_pipes) C++11
0 / 100
 1492 ms 3120 KB 
#include<bits/stdc++.h>

using namespace std;

int N, M, lev[100009], up[100009];

int E = 0, y[400009], lst[100009], prv[400009];
void addEdge (int a, int b)
{
    y[++E] = b;
    if (lst[a] == 0) lst[a] = E;
    else prv[E] = lst[a], lst[a] = E;

    y[++E] = a;
    if (lst[b] == 0) lst[b] = E;
    else prv[E] = lst[b], lst[b] = E;
}

int t[2][100009];
int tata (int lin, int i)
{
    if (t[lin][i] == i) return i;
    return t[lin][i] = tata (lin, t[lin][i]);
}

void dfs (int nod, int tata)
{
    up[nod] = lev[nod];
    for (int e = lst[nod]; e != 0; e = prv[e])
    {
        int it = y[e];
        if (lev[it] == 0)
        {
            lev[it] = lev[nod] + 1;
            dfs (it, nod);
            if (up[it] > lev[nod])
                printf ("%d %d\n", it, nod);
        }
    }
    bool firstException = 1;
    for (int e = lst[nod]; e != 0; e = prv[e])
    {
        int it = y[e];
        if (it == tata && firstException == 1) firstException = 0;
        else
        if (up[it] < up[nod]) up[nod] = up[it];
    }
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d", &N, &M);
for (int i=1; i<=N; i++)
    t[0][i] = t[1][i] = i;
while (M --)
{
    int x, y;
    scanf ("%d %d", &x, &y);
    if (tata (0, x) != tata (0, y))
        t[0][tata (0, x)] = tata (0, y),
        addEdge (x, y);
    else
    if (tata (1, x) != tata (1, y))
        t[1][tata (1, x)] = tata (1, y);
}
assert (E < 2 * N);
return 0;
for (int i=1; i<=N; i++)
    if (tata (1, i) != i)
        addEdge (tata (1, i), i);
for (int i=1; i<=N; i++)
    if (lev[i] == 0)
        lev[i] = 1, dfs (i, -1);
return 0;
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d %d", &N, &M);
 ~~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:61:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &x, &y);
     ~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 384 KB Output is correct
2 Incorrect 113 ms 512 KB Wrong number of edges

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 640 KB Output is correct
2 Incorrect 230 ms 640 KB Wrong number of edges

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 1016 KB Output is correct
2 Incorrect 272 ms 1168 KB Wrong number of edges

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 2284 KB Output is correct
2 Incorrect 403 ms 2268 KB Wrong number of edges

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 2528 KB Output is correct
2 Incorrect 660 ms 2524 KB Wrong number of edges

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 894 ms 3036 KB Output is correct
2 Incorrect 851 ms 3064 KB Wrong number of edges

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1131 ms 3120 KB Output is correct
2 Incorrect 1066 ms 3060 KB Wrong number of edges

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1492 ms 2940 KB Output is correct
2 Incorrect 1379 ms 3064 KB Wrong number of edges