| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 90118 | 2018-12-20T11:57:22 Z | cs71107 | 간선 파괴 (GA5_destroy) | C++14 | 68 ms | 22752 KB |
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<int, pii> piii;
const int INF = 1e9+1;
const int MAXN = 2e5+10;
const int MAXM = 7e2+10;
priority_queue<int> pq;
int par[MAXN];
int par1[MAXN];
pii edge[MAXN];
int L[MAXN];
int R[MAXN];
int mst[MAXM];
int rvmst[MAXM];
int component[MAXM][MAXM];
void init(int V)
{
for(int i=1;i<=V;i++)par[i] = i;
return;
}
int root(int x)
{
if(x==par[x])return x;
else return par[x] = root(par[x]);
}
bool mymerge(int x,int y)
{
x = root(x);
y = root(y);
if(x==y)return false;
//if(x>y)swap(x,y);
par[y] = x;
return true;
}
int main()
{
int V,E;
int x,y;
int mstcnt = 1;
int rvmstcnt = 1;
scanf("%d%d",&V,&E);
init(V);
for(int i=1;i<=E;i++)scanf("%d%d",&edge[i].first,&edge[i].second);
for(int i=1;i<=E;i++){
x = edge[i].first;
y = edge[i].second;
if(!mymerge(x,y))continue;
mst[mstcnt++] = i;
}
init(V);
for(int i=E;i>=1;i--){
x = edge[i].first;
y = edge[i].second;
if(!mymerge(x,y))continue;
rvmst[rvmstcnt++] = i;
}
init(V);
int nw,rnw,x1,y1;
for(int i=0;i<mstcnt;i++)
{
nw = mst[i];
x = edge[nw].first;
y = edge[nw].second;
mymerge(x,y);
component[i][0] = V-i;
for(int j=1;j<=V;j++)par1[j] = par[j];
for(int j=1;j<rvmstcnt;j++){
rnw = rvmst[j];
x1 = edge[rnw].first;
y1 = edge[rnw].second;
if(mymerge(x1,y1))component[i][j] = component[i][j-1]-1;
else component[i][j] = component[i][j-1];
}
for(int j=1;j<=V;j++)par[j] = par1[j];
}
for(int i=1;i<mstcnt;i++)nw = mst[i], L[nw] = i;
for(int i=1;i<rvmstcnt;i++)nw = rvmst[i], R[nw] = i;
for(int i=1;i<=E;i++)L[i] = max(L[i],L[i-1]);
for(int i=E;i>=1;i--)R[i] = max(R[i],R[i+1]);
int q;
scanf("%d",&q);
int a,b;
for(int i=1;i<=q;i++)
{
scanf("%d%d",&a,&b);
printf("%d\n",component[L[a-1]][R[b+1]]);
}
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 760 KB | Output is correct |
| 2 | Correct | 2 ms | 760 KB | Output is correct |
| 3 | Correct | 2 ms | 824 KB | Output is correct |
| 4 | Correct | 3 ms | 824 KB | Output is correct |
| 5 | Correct | 3 ms | 824 KB | Output is correct |
| 6 | Correct | 2 ms | 824 KB | Output is correct |
| 7 | Correct | 3 ms | 844 KB | Output is correct |
| 8 | Correct | 2 ms | 844 KB | Output is correct |
| 9 | Correct | 3 ms | 936 KB | Output is correct |
| 10 | Correct | 3 ms | 1000 KB | Output is correct |
| 11 | Correct | 2 ms | 1004 KB | Output is correct |
| 12 | Correct | 2 ms | 1012 KB | Output is correct |
| 13 | Correct | 2 ms | 1012 KB | Output is correct |
| 14 | Correct | 2 ms | 1012 KB | Output is correct |
| 15 | Correct | 2 ms | 1040 KB | Output is correct |
| 16 | Correct | 2 ms | 1040 KB | Output is correct |
| 17 | Correct | 2 ms | 1048 KB | Output is correct |
| 18 | Correct | 2 ms | 1048 KB | Output is correct |
| 19 | Correct | 2 ms | 1048 KB | Output is correct |
| 20 | Correct | 2 ms | 1048 KB | Output is correct |
| 21 | Correct | 2 ms | 1048 KB | Output is correct |
| 22 | Correct | 2 ms | 1048 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 14 ms | 2740 KB | Output is correct |
| 2 | Correct | 12 ms | 2740 KB | Output is correct |
| 3 | Correct | 14 ms | 3008 KB | Output is correct |
| 4 | Correct | 23 ms | 3952 KB | Output is correct |
| 5 | Correct | 22 ms | 4336 KB | Output is correct |
| 6 | Correct | 30 ms | 4984 KB | Output is correct |
| 7 | Correct | 29 ms | 5584 KB | Output is correct |
| 8 | Correct | 28 ms | 6040 KB | Output is correct |
| 9 | Correct | 11 ms | 6040 KB | Output is correct |
| 10 | Correct | 10 ms | 6040 KB | Output is correct |
| 11 | Correct | 10 ms | 6040 KB | Output is correct |
| 12 | Correct | 22 ms | 6552 KB | Output is correct |
| 13 | Correct | 22 ms | 6948 KB | Output is correct |
| 14 | Correct | 22 ms | 7336 KB | Output is correct |
| 15 | Correct | 10 ms | 7336 KB | Output is correct |
| 16 | Correct | 11 ms | 7336 KB | Output is correct |
| 17 | Correct | 6 ms | 7336 KB | Output is correct |
| 18 | Correct | 6 ms | 7336 KB | Output is correct |
| 19 | Correct | 4 ms | 7336 KB | Output is correct |
| 20 | Correct | 4 ms | 7336 KB | Output is correct |
| 21 | Correct | 3 ms | 7336 KB | Output is correct |
| 22 | Correct | 3 ms | 7336 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 48 ms | 9272 KB | Output is correct |
| 2 | Correct | 47 ms | 10140 KB | Output is correct |
| 3 | Correct | 68 ms | 12812 KB | Output is correct |
| 4 | Correct | 49 ms | 12812 KB | Output is correct |
| 5 | Correct | 43 ms | 13116 KB | Output is correct |
| 6 | Correct | 66 ms | 16064 KB | Output is correct |
| 7 | Correct | 42 ms | 16064 KB | Output is correct |
| 8 | Correct | 44 ms | 16164 KB | Output is correct |
| 9 | Correct | 35 ms | 16208 KB | Output is correct |
| 10 | Correct | 34 ms | 16652 KB | Output is correct |
| 11 | Correct | 42 ms | 17772 KB | Output is correct |
| 12 | Correct | 68 ms | 20856 KB | Output is correct |
| 13 | Correct | 53 ms | 21096 KB | Output is correct |
| 14 | Correct | 50 ms | 22328 KB | Output is correct |
| 15 | Correct | 35 ms | 22328 KB | Output is correct |
| 16 | Correct | 36 ms | 22328 KB | Output is correct |
| 17 | Correct | 29 ms | 22328 KB | Output is correct |
| 18 | Correct | 25 ms | 22448 KB | Output is correct |
| 19 | Correct | 19 ms | 22448 KB | Output is correct |
| 20 | Correct | 20 ms | 22752 KB | Output is correct |
| 21 | Correct | 16 ms | 22752 KB | Output is correct |
| 22 | Correct | 16 ms | 22752 KB | Output is correct |