oj.uz

Submission #129688

# Submission time Handle Problem Language Result Execution time Memory
129688 2019-07-13T04:42:43 Z 김세빈(#3138) 물병 (JOI14_bottle) C++14
30 / 100
 873 ms 56004 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;
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])){
					unite(C[t], C[p]);
					K.emplace_back(C[p], C[t], D[t] + D[p]);
				}
			}
			x -= dx[i]; y -= dy[i];
		}
	}
	
	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:71:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0; i<K.size(); i++){
            ~^~~~~~~~~
bottle.cpp:77:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     V[S[i] + E[i] >> 1].push_back(i);
       ~~~~~^~~~~~
bottle.cpp:84:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0; i<K.size(); i++){
            ~^~~~~~~~~
bottle.cpp:88:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
      E[t] = (S[t] + E[t] >> 1) - 1;
              ~~~~~^~~~~~
bottle.cpp:90:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     else S[t] = (S[t] + E[t] >> 1) + 1;
                  ~~~~~^~~~~~
bottle.cpp:96: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:62: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 5368 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 10744 KB Output is correct
2 Correct 45 ms 8952 KB Output is correct
3 Correct 404 ms 40616 KB Output is correct
4 Correct 626 ms 40796 KB Output is correct
5 Correct 689 ms 41108 KB Output is correct
6 Correct 433 ms 40824 KB Output is correct
7 Correct 618 ms 40720 KB Output is correct
8 Correct 710 ms 41056 KB Output is correct
9 Correct 873 ms 41324 KB Output is correct
10 Correct 501 ms 40696 KB Output is correct
11 Correct 566 ms 40704 KB Output is correct
12 Correct 170 ms 34040 KB Output is correct
13 Correct 242 ms 33784 KB Output is correct
14 Correct 164 ms 33964 KB Output is correct
15 Correct 225 ms 33852 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

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