oj.uz

Submission #129699

# Submission time Handle Problem Language Result Execution time Memory
129699 2019-07-13T05:00:54 Z 김세빈(#3138) 물병 (JOI14_bottle) C++14
30 / 100
 889 ms 56408 KB 
#include <bits/stdc++.h>

using namespace std;

struct edge{
	int u, v, c;
	edge() {}
	edge(int u, int v, int c) : u(u), v(v), c(c) {}
};

char B[2020][2020];
queue <int> Q;
vector <edge> K, T;
vector <int> V[202020];
int C[4040404], D[4040404], P[202020];
int X[202020], Y[202020], S[202020], E[202020];
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int n, m, k, q;

int find(int p) { return p == P[p]? p : P[p] = find(P[p]); }
void unite(int p, int q) { P[find(p)] = find(q); }

int main()
{
	int i, x, y, p, t, f;
	
	scanf("%d%d%d%d", &n, &m, &k, &q);
	
	for(i=0; i<n; i++){
		scanf("%s", B[i]);
	}
	
	for(i=1; i<=k; i++){
		scanf("%d%d", &x, &y);
		x --; y --; t = x * m + y;
		Q.push(t); C[t] = i; D[t] = 0;
		P[i] = i;
	}
	
	for(; !Q.empty(); ){
		p = Q.front(); Q.pop();
		x = p / m; y = p % m;
		
		for(i=0; i<4; i++){
			x += dx[i]; y += dy[i];
			if(0 <= x && x < n && 0 <= y && y < m && B[x][y] == '.'){
				t = x * m + y;
				if(!C[t]) Q.push(t), C[t] = C[p], D[t] = D[p] + 1;
				else if(find(C[t]) != find(C[p])){
					if(D[t] == D[p]){
						unite(C[t], C[p]);
						K.emplace_back(C[p], C[t], D[t] + D[p]);
					}
					else if(D[t] == D[p] + 1){
						T.emplace_back(C[p], C[t], D[t] + D[p]);
					}
				}
			}
			x -= dx[i]; y -= dy[i];
		}
		
		for(edge &x: T){
			if(find(x.u) != find(x.v)){
				unite(x.u, x.v);
				K.push_back(x);
			}
		}
		
		T.clear();
	}
	
	sort(K.begin(), K.end(), [&](edge &ea, edge &eb){
		return ea.c < eb.c;
	});
	
	for(i=1; i<=q; i++){
		scanf("%d%d", X + i, Y + i);
		S[i] = 0; E[i] = K.size() - 1;
	}
	
	for(; ; ){
		for(i=1; i<=k; i++){
			P[i] = i;
		}
		
		for(i=0; i<K.size(); i++){
			V[i].clear();
		}
		
		for(i=1, f=0; i<=q; i++){
			if(S[i] <= E[i]){
				V[S[i] + E[i] >> 1].push_back(i);
				f = 1;
			}
		}
		
		if(!f) break;
		
		for(i=0; i<K.size(); i++){
			unite(K[i].u, K[i].v);
			for(int &t: V[i]){
				if(find(X[t]) == find(Y[t])){
					E[t] = (S[t] + E[t] >> 1) - 1;
				}
				else S[t] = (S[t] + E[t] >> 1) + 1;
			}
		}
	}
	
	for(i=1; i<=q; i++){
		if(E[i] + 1 < K.size()) printf("%d\n", K[E[i] + 1].c);
		else printf("-1\n");
	}
		
	return 0;
}

Compilation message

bottle.cpp: In function 'int main()':
bottle.cpp:86:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0; i<K.size(); i++){
            ~^~~~~~~~~
bottle.cpp:92:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     V[S[i] + E[i] >> 1].push_back(i);
       ~~~~~^~~~~~
bottle.cpp:99:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0; i<K.size(); i++){
            ~^~~~~~~~~
bottle.cpp:103:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
      E[t] = (S[t] + E[t] >> 1) - 1;
              ~~~~~^~~~~~
bottle.cpp:105:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     else S[t] = (S[t] + E[t] >> 1) + 1;
                  ~~~~~^~~~~~
bottle.cpp:111:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(E[i] + 1 < K.size()) printf("%d\n", K[E[i] + 1].c);
      ~~~~~~~~~^~~~~~~~~~
bottle.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &n, &m, &k, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", B[i]);
   ~~~~~^~~~~~~~~~~~
bottle.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~
bottle.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", X + i, Y + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 10920 KB Output is correct
2 Correct 48 ms 9208 KB Output is correct
3 Correct 460 ms 41324 KB Output is correct
4 Correct 689 ms 41368 KB Output is correct
5 Correct 736 ms 41496 KB Output is correct
6 Correct 444 ms 41120 KB Output is correct
7 Correct 671 ms 41264 KB Output is correct
8 Correct 766 ms 41636 KB Output is correct
9 Correct 889 ms 41568 KB Output is correct
10 Correct 531 ms 40992 KB Output is correct
11 Correct 619 ms 41208 KB Output is correct
12 Correct 181 ms 34332 KB Output is correct
13 Correct 232 ms 34252 KB Output is correct
14 Correct 176 ms 34420 KB Output is correct
15 Correct 227 ms 34240 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

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