oj.uz

Submission #2846

# Submission time Handle Problem Language Result Execution time Memory
2846 2013-07-31T15:43:47 Z ansol4328 간선 파괴 (GA5_destroy) C++
25 / 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;
    }
    scanf("%d",&que);
    for(i=1 ; i<=que ; i++)
    {
        scanf("%d %d",&a,&b);
		printf("%d\n",bfs(a,b));
    }
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory 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 Correct 0 ms 3012 KB Output is correct
11 Correct 0 ms 3012 KB Output is correct
12 Correct 0 ms 3012 KB Output is correct
13 Correct 0 ms 3012 KB Output is correct
14 Correct 0 ms 3012 KB Output is correct
15 Correct 0 ms 3012 KB Output is correct
16 Correct 0 ms 3012 KB Output is correct
17 Correct 0 ms 3012 KB Output is correct
18 Correct 0 ms 3012 KB Output is correct
19 Correct 0 ms 3012 KB Output is correct
20 Correct 0 ms 3012 KB Output is correct
21 Correct 0 ms 3012 KB Output is correct
22 Correct 0 ms 3012 KB Output is correct

Subtask #2
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1556 ms 3012 KB Output is correct
2 Correct 1476 ms 3012 KB Output is correct
3 Correct 1652 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

# Verdict Execution time Memory Grader output
1 Execution timed out 2500 ms 3012 KB Program timed out
2 Halted 0 ms 0 KB -