oj.uz

Submission #2998

# Submission time Handle Problem Language Result Execution time Memory
2998 2013-08-21T10:33:59 Z cki86201 간선 파괴 (GA5_destroy) C++
100 / 100
 1764 ms 5728 KB 
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<math.h>
#include<stdlib.h>
#include<queue>
#include<functional>
using namespace std;

//slow O(QV) method;

const int ME = 250000;
const int MV = 710;
const int INF = 0x7fffffff;
int st[MV], en[ME], next[ME], sen[ME];
int nst[MV], nen[4*MV], nnext[4*MV],num[4*MV];
int E,V;
int MST[MV][2];	//0:minimum, 1:maximum;
int L[2];
int Q;
int chk[MV];
bool check[MV];
struct edge{
	edge(){}
	edge(int en,int len):en(en),len(len){}
	int en,len;
	bool operator>(const edge &l)const{
		return len>l.len;
	}
};
priority_queue <edge, vector<edge>, greater<edge> > heap;

void addedge(int s,int d,int c)
{
	next[c]=st[s];
	st[s]=c;
	en[c]=d;
	sen[c]=s;
}

void naddedge(int s,int d,int c)
{
	nnext[c]=nst[s];
	nst[s]=c;
	nen[c]=d;
}

void find_MST(int x)
{
	memset(check,0,sizeof(check));
	int t=x?-1:1;
	int ct=0;
	while(!heap.empty())heap.pop();
	int u;
	for(u=1;u<=V;u++){
		if(check[u])continue;
		heap.push(edge(u,INF));
		while(!heap.empty() && ct!=V){
			edge tx = heap.top();
			heap.pop();
			if(check[tx.en])continue;
			check[tx.en]=1;
			if(tx.len!=INF)MST[++L[x]][x]=tx.len*t;
			int i;
			for(i=st[tx.en];i;i=next[i]){
				int ttx = en[i];
				if(check[ttx])continue;
				heap.push(edge(en[i],i/2*t));
			}
			ct++;
		}
	}
	for(int i=1;i<=L[x];i++){
		int c=i;
		if(x)c+=L[0];
		int mx = MST[i][x]*2;
		naddedge(sen[mx],en[mx],2*c);
		num[2*c]=mx/2;
		naddedge(en[mx],sen[mx],2*c+1);
		num[2*c+1]=mx/2;
	}
}

void dfs(int x,int s,int d)
{
	chk[x]=Q+1;
	int i;
	for(i=nst[x];i;i=nnext[i]){
		if(chk[nen[i]]==Q+1)continue;
		if(num[i]>=s&&num[i]<=d)continue;
		dfs(nen[i],s,d);
	}
}

void solve(int s,int d)
{
	int i,ans=0;
	for(i=1;i<=V;i++){
		if(chk[i]==Q+1)continue;
		dfs(i,s,d);
		ans++;
	}
	printf("%d\n",ans);
}

int main()
{
	scanf("%d%d",&V,&E);
	int i;
	for(i=1;i<=E;i++){
		int x,y;scanf("%d%d",&x,&y);
		addedge(x,y,2*i);
		addedge(y,x,2*i+1);
	}
	find_MST(0);
	find_MST(1);
	scanf("%d",&Q);
	while(Q--){
		int x,y;scanf("%d%d",&x,&y);
		solve(x,y);
	}
	return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4188 KB Output is correct
2 Correct 0 ms 4188 KB Output is correct
3 Correct 0 ms 4188 KB Output is correct
4 Correct 0 ms 4188 KB Output is correct
5 Correct 0 ms 4188 KB Output is correct
6 Correct 0 ms 4188 KB Output is correct
7 Correct 0 ms 4188 KB Output is correct
8 Correct 0 ms 4188 KB Output is correct
9 Correct 0 ms 4188 KB Output is correct
10 Correct 0 ms 4188 KB Output is correct
11 Correct 0 ms 4188 KB Output is correct
12 Correct 0 ms 4188 KB Output is correct
13 Correct 0 ms 4188 KB Output is correct
14 Correct 0 ms 4188 KB Output is correct
15 Correct 0 ms 4188 KB Output is correct
16 Correct 0 ms 4188 KB Output is correct
17 Correct 0 ms 4188 KB Output is correct
18 Correct 0 ms 4188 KB Output is correct
19 Correct 0 ms 4188 KB Output is correct
20 Correct 0 ms 4188 KB Output is correct
21 Correct 0 ms 4188 KB Output is correct
22 Correct 0 ms 4188 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4320 KB Output is correct
2 Correct 28 ms 4320 KB Output is correct
3 Correct 24 ms 4320 KB Output is correct
4 Correct 32 ms 4960 KB Output is correct
5 Correct 36 ms 4960 KB Output is correct
6 Correct 220 ms 4960 KB Output is correct
7 Correct 212 ms 4960 KB Output is correct
8 Correct 208 ms 4960 KB Output is correct
9 Correct 44 ms 4188 KB Output is correct
10 Correct 44 ms 4188 KB Output is correct
11 Correct 40 ms 4188 KB Output is correct
12 Correct 36 ms 4960 KB Output is correct
13 Correct 32 ms 4960 KB Output is correct
14 Correct 40 ms 4960 KB Output is correct
15 Correct 44 ms 4188 KB Output is correct
16 Correct 48 ms 4188 KB Output is correct
17 Correct 36 ms 4188 KB Output is correct
18 Correct 28 ms 4188 KB Output is correct
19 Correct 16 ms 4188 KB Output is correct
20 Correct 16 ms 4188 KB Output is correct
21 Correct 0 ms 4188 KB Output is correct
22 Correct 4 ms 4188 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 764 ms 4960 KB Output is correct
2 Correct 756 ms 4960 KB Output is correct
3 Correct 720 ms 5728 KB Output is correct
4 Correct 748 ms 4960 KB Output is correct
5 Correct 848 ms 4576 KB Output is correct
6 Correct 716 ms 5728 KB Output is correct
7 Correct 844 ms 4576 KB Output is correct
8 Correct 880 ms 4576 KB Output is correct
9 Correct 1492 ms 4188 KB Output is correct
10 Correct 1484 ms 4188 KB Output is correct
11 Correct 796 ms 4576 KB Output is correct
12 Correct 716 ms 5728 KB Output is correct
13 Correct 732 ms 5728 KB Output is correct
14 Correct 696 ms 5728 KB Output is correct
15 Correct 1688 ms 4188 KB Output is correct
16 Correct 1764 ms 4188 KB Output is correct
17 Correct 1400 ms 4188 KB Output is correct
18 Correct 1324 ms 4188 KB Output is correct
19 Correct 576 ms 4188 KB Output is correct
20 Correct 776 ms 4188 KB Output is correct
21 Correct 212 ms 4188 KB Output is correct
22 Correct 216 ms 4188 KB Output is correct