This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
cptable[edge[j].end] = cptable[edge[j].start];
}
for(int j = 1; j <= E; 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]);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |