oj.uz

Submission #54370

# Submission time Handle Problem Language Result Execution time Memory
54370 2018-07-03T09:18:30 Z Costin Andrei Oncescu(#1303) Pipes (CEOI15_pipes) C++11
100 / 100
 1371 ms 5504 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);
}
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
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 540 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 488 KB Output is correct
2 Correct 110 ms 484 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 780 KB Output is correct
2 Correct 234 ms 776 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 1544 KB Output is correct
2 Correct 280 ms 1708 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 3832 KB Output is correct
2 Correct 386 ms 3832 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 709 ms 4364 KB Output is correct
2 Correct 667 ms 3832 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 980 ms 5384 KB Output is correct
2 Correct 861 ms 5404 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1231 ms 5504 KB Output is correct
2 Correct 1145 ms 5368 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1371 ms 5124 KB Output is correct
2 Correct 1359 ms 4572 KB Output is correct