oj.uz

Submission #43304

# Submission time Handle Problem Language Result Execution time Memory
43304 2018-03-13T10:11:48 Z ffresh 물병 (JOI14_bottle) C++14
0 / 100
 5000 ms 180708 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 4005,M = 2e5+15,LIM = 2e6+5;

int px[M],py[M];

int org[N][N],T[N][N];

int par[M];

int f(int x){
	if(x==par[x])return x;
	return par[x]= f(par[x]);
}
int xlim ,ylim;

int check(int ny,int nx){
	if(nx>=1 && ny>=1 && nx<=xlim && ny<=ylim)return 1;
	return 0;
}
void color(){
	for(int i=1;i<=ylim;++i)
		for(int j=1;j<=xlim;++j)
			T[i][j] = org[i][j];
}

void merge(int a,int b){
	a= f(a),b = f(b);
	if(a==b)return;
	par[b]= a;
}
vector<int> ch[LIM];


bool cor[M];
int L[M],R[M];

int start[M],tar[M];

int dy[4]= {1,-1,0,0},dx[4]= {0,0,1,-1};

int main(){
	//freopen("input.txt","r",stdin);
	int h,w,p,q;
	cin>>h>>w>>p>>q;
	string s;
	 xlim = w*2,ylim = h*2;
	for(int i=1;i<=h;++i){
		cin>>s;
		for(int j=1;j<=w;++j){
			if(s[j-1]=='#'){
				org[i*2-1][j*2-1] = -1;
                org[i*2-1][j*2]= -1;
                org[i*2][j*2-1]= -1;
                org[i*2][j*2]= -1;
			}
		}
	}
	for(int i=1;i<=p;++i){
		scanf("%d%d",&py[i],&px[i]);
		px[i] = px[i]*2-1,py[i]= py[i]*2-1;
		org[py[i]][px[i]]= i;
	}
	for(int i=1;i<=q;++i){
		scanf("%d%d",&start[i],&tar[i]);
		L[i]= 0,R[i] = LIM-1;
	}
	bool is = 1;
	while(is){
		is=0;
		color();
		stack<pair<int,pair<int,int> > >st;
		
		for(int i=1;i<=p;++i){
            par[i]= i;
			st.push(make_pair(i,make_pair(py[i],px[i])));
		}
		for(int i=1;i<=q;++i){
			if(L[i]==R[i])continue;
			int mid = (L[i] + R[i])/2;
			is = 1;
			ch[mid].push_back(i);
		}
        
		stack<pair<int,pair<int,int> > >temp;

		int ny,nx,a,b,len = 0,cur;
		while(!st.empty()){
			++len;
            
			while(!st.empty()){
				int id = st.top().first;
				a= st.top().second.first, b= st.top().second.second;
                st.pop();
				for(int i=0;i<4;++i){
					ny = a+dy[i],nx =b+dx[i];
					if(T[ny][nx]==0){
					 	if(check(ny,nx)){
							T[ny][nx]=id;
							 temp.push(make_pair(id,make_pair(ny,nx)));
						}
					}
					else if(T[ny][nx]!=-1){
						merge(T[ny][nx],id);
					}
				}
			}
            
			swap(st,temp);
			cur = (len-1)/2;
			cur*=2;
			
			if(len%2 ==0)
				++cur;
			while(!ch[cur].empty()){
				a = ch[cur].back();
				ch[cur].pop_back();
				if(f(start[a]) == f(tar[a])){
					R[a] = cur;
				}
				else{
					L[a]= cur+1;
                    cor[a]= 1;
                }
            }
		}
        
		for(int i=cur;i<LIM;++i){
			while(!ch[i].empty()){
				a= ch[i].back();
				R[a]= i;
				ch[i].pop_back();
			}
		}
	}
	for(int i=1;i<=q;++i){
        if(cor[i])
		    printf("%d\n",L[i]);
        else
            printf("-1\n");
	}

}

Compilation message

bottle.cpp: In function 'int main()':
bottle.cpp:62:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&py[i],&px[i]);
                              ^
bottle.cpp:67:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&start[i],&tar[i]);
                                  ^

Subtask #1
0 / 10.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5094 ms 180708 KB Time limit exceeded
2 Halted 0 ms 0 KB -