oj.uz

답안 #2818

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
2818 2013-07-31T13:18:14 Z ansol4328 간선 파괴 (GA5_destroy) C++
0 / 100
 2500 ms 3012 KB 
#include<stdio.h>
#include<memory.h>
#include<stdlib.h>

int n, m, xy[702][702];
int cnt;

int bfs(int l, int e)
{
    int q[702], check[702], f, r, num;
    int i ,j;
    int c=0;

    memset(check,0,sizeof(check));
    for(i=1 ; i<=n ; i++)
    {
        if(check[i]==0)
        {
            c++;
            f=0;
            r=1;
            q[r]=i;
            check[i]=1;
            do
            {
                f++;
                num=q[f];
                for(j=1 ; j<=n ; j++)
                {
                    if((xy[num][j]!=0 && xy[num][j]<l && check[j]==0) || (xy[num][j]!=0 && xy[num][j]>e && check[j]==0))
                    {
                        r++;
                        q[r]=j;
                        check[j]=1;
                    }
                }
            }while(f<r);
        }
    }
    return c;
}

int main()
{
    int a, b, i, que;
    int max;

    scanf("%d %d",&n,&m);
    for(i=1 ; i<=m ; i++)
    {
        scanf("%d %d",&a,&b);
        xy[a][b]=i;
		xy[b][a]=i;
    }
    max=bfs(0,0);
    scanf("%d",&que);
    for(i=1 ; i<=que ; i++)
    {
        scanf("%d %d",&a,&b);
		printf("%d\n",bfs(a,b)-max+1);
    }
    return 0;
}

Subtask #1
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 3012 KB Output is correct
2 Correct 0 ms 3012 KB Output is correct
3 Correct 0 ms 3012 KB Output is correct
4 Correct 0 ms 3012 KB Output is correct
5 Correct 0 ms 3012 KB Output is correct
6 Correct 0 ms 3012 KB Output is correct
7 Correct 4 ms 3012 KB Output is correct
8 Correct 0 ms 3012 KB Output is correct
9 Correct 0 ms 3012 KB Output is correct
10 Incorrect 0 ms 3012 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1560 ms 3012 KB Output is correct
2 Correct 1496 ms 3012 KB Output is correct
3 Correct 1660 ms 3012 KB Output is correct
4 Execution timed out 2500 ms 3012 KB Program timed out
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2084 ms 3012 KB Program hung waiting for input
2 Halted 0 ms 0 KB -