Submission #2807

#	Time	Username	Problem	Language	Result	Execution time	Memory
2807		mhkim4886	간선 파괴 (GA5_destroy)	C++98	0 / 100	2500 ms	3672 KiB

destroy

#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].start] = k;
            cptable[edge[j].end] = 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 ", component[i]);
    }
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 35
• Subtask 3: 0 / 40