Submission #54386

#	Time	Username	Problem	Language	Result	Execution time	Memory
54386		admin	Pipes (CEOI15_pipes)	C++14	100 / 100	1474 ms	5504 KiB

pipes

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10