oj.uz

Submission #54368

# Submission time Handle Problem Language Result Execution time Memory
54368 2018-07-03T09:11:24 Z Costin Andrei Oncescu(#1303) Pipes (CEOI15_pipes) C++11
100 / 100
 1450 ms 8132 KB 
#include<bits/stdc++.h>

using namespace std;

int N, M, lev[100009], up[100009];
vector < int > v[100009];

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 (auto it : v[nod])
        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 (auto it : v[nod])
        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),
        v[x].push_back (y),
        v[y].push_back (x);
    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)
        v[tata (1, i)].push_back (i),
        v[i].push_back (tata (1, 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:38: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:44: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 4 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2944 KB Output is correct
2 Correct 8 ms 2916 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 2856 KB Output is correct
2 Correct 114 ms 2852 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 3228 KB Output is correct
2 Correct 237 ms 3216 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 4040 KB Output is correct
2 Correct 291 ms 4376 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 6460 KB Output is correct
2 Correct 413 ms 6588 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 733 ms 7024 KB Output is correct
2 Correct 703 ms 6880 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1014 ms 8132 KB Output is correct
2 Correct 911 ms 8028 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1193 ms 8124 KB Output is correct
2 Correct 1189 ms 8044 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1450 ms 7800 KB Output is correct
2 Correct 1415 ms 7936 KB Output is correct