oj.uz

Submission #2796

# Submission time Handle Problem Language Result Execution time Memory
2796 2013-07-31T11:36:27 Z mhkim4886 간선 파괴 (GA5_destroy) C++
0 / 100
 2500 ms 3668 KB 
#include <stdio.h>
#include <algorithm>

typedef struct _edge
{
    int start, end;
    int num;
} Edge;

bool Compare(const Edge &a, const Edge &b)
{
    return a.start < b.start;
}

int main()
{
    int V, E, Q, dst[60000][3];
    Edge edge[150000];
    scanf("%d %d", &V, &E);

    for(int i = 1; i <= E; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);

        if(a <= b)
        {
            edge[i].start = a;
            edge[i].end = b;
            edge[i].num = i;
        }
        else
        {
            edge[i].start = b;
            edge[i].end = a;
            edge[i].num = i;
        }
    }

    scanf("%d", &Q);
    for(int i = 1; i <= Q; i++) scanf("%d %d", &dst[i][1], &dst[i][2]);
    std::sort(edge+1, edge+1+E, Compare);

    int cptable[1000], counter[1000], component[60000];
    for(int i = 1; i <= Q; i++)
    {
        for(int j = 1; j <= V; j++)
        {
            cptable[j] = j;
            counter[j] = 0;
        }

        int components = 0;
        for(int j = 1; j <= E; j++)
        {
            if(dst[i][1] <= edge[j].num && edge[j].num <= dst[i][2]) continue;
            int k = cptable[edge[j].start] < cptable[edge[j].end] ? cptable[edge[j].start] : cptable[edge[j].end];
            cptable[edge[j].end] = cptable[edge[j].start] = k;
        }

        for(int j = 1; j <= V; j++)
        {
            if(counter[cptable[j]] == 0) components++;
            counter[cptable[j]] = 1;
        }

        component[i] = components;
    }

    for(int i = 1; i <= Q; i++) printf("%d\n", component[i]);
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 196 ms 3668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

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