oj.uz

답안 #54796

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
54796 2018-07-05T05:48:38 Z 나는야 테스트(#2061) Pipes (CEOI15_pipes) C++11
100 / 100
 1411 ms 5400 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 512 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 488 KB Output is correct
2 Correct 110 ms 488 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 197 ms 776 KB Output is correct
2 Correct 237 ms 772 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 327 ms 1540 KB Output is correct
2 Correct 272 ms 1652 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 431 ms 3820 KB Output is correct
2 Correct 383 ms 3832 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 683 ms 4372 KB Output is correct
2 Correct 666 ms 3832 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1124 ms 5388 KB Output is correct
2 Correct 881 ms 5400 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1142 ms 5388 KB Output is correct
2 Correct 1090 ms 5396 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1411 ms 5124 KB Output is correct
2 Correct 1337 ms 4644 KB Output is correct