oj.uz

Submission #129709

# Submission time Handle Problem Language Result Execution time Memory
129709 2019-07-13T05:18:49 Z 김세빈(#3138) 물병 (JOI14_bottle) C++14
100 / 100
 1681 ms 64980 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;
		
		if(!T.empty() && D[p] + D[p] > T.back().c){
			for(edge &x: T){
				if(find(x.u) != find(x.v)){
					unite(x.u, x.v);
					K.push_back(x);
				}
			}
			
			T.clear();
		}
		
		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 T.emplace_back(C[p], C[t], D[t] + D[p]);
				}
			}
			x -= dx[i]; y -= dy[i];
		}
	}
	
	for(i=1; i<K.size(); i++){
		if(K[i].c < K[i - 1].c) for(; ; );
	}
	
	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:72:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=1; i<K.size(); i++){
           ~^~~~~~~~~
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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5368 KB Output is correct
2 Correct 10 ms 5752 KB Output is correct
3 Correct 11 ms 6008 KB Output is correct
4 Correct 126 ms 16676 KB Output is correct
5 Correct 123 ms 15992 KB Output is correct
6 Correct 125 ms 16028 KB Output is correct
7 Correct 125 ms 16480 KB Output is correct
8 Correct 129 ms 16808 KB Output is correct
9 Correct 125 ms 16716 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 10616 KB Output is correct
2 Correct 47 ms 8952 KB Output is correct
3 Correct 432 ms 40716 KB Output is correct
4 Correct 623 ms 40748 KB Output is correct
5 Correct 762 ms 41208 KB Output is correct
6 Correct 502 ms 40780 KB Output is correct
7 Correct 634 ms 40824 KB Output is correct
8 Correct 722 ms 41208 KB Output is correct
9 Correct 769 ms 41136 KB Output is correct
10 Correct 523 ms 40444 KB Output is correct
11 Correct 598 ms 40704 KB Output is correct
12 Correct 180 ms 34096 KB Output is correct
13 Correct 225 ms 33784 KB Output is correct
14 Correct 170 ms 34012 KB Output is correct
15 Correct 224 ms 33884 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 10744 KB Output is correct
2 Correct 41 ms 8696 KB Output is correct
3 Correct 315 ms 40984 KB Output is correct
4 Correct 658 ms 41248 KB Output is correct
5 Correct 738 ms 41516 KB Output is correct
6 Correct 816 ms 41344 KB Output is correct
7 Correct 465 ms 41080 KB Output is correct
8 Correct 602 ms 41412 KB Output is correct
9 Correct 179 ms 34680 KB Output is correct
10 Correct 236 ms 34552 KB Output is correct
11 Correct 220 ms 33912 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 55792 KB Output is correct
2 Correct 1236 ms 63564 KB Output is correct
3 Correct 453 ms 40596 KB Output is correct
4 Correct 1568 ms 64804 KB Output is correct
5 Correct 1681 ms 64980 KB Output is correct
6 Correct 866 ms 57108 KB Output is correct
7 Correct 490 ms 40568 KB Output is correct
8 Correct 166 ms 33740 KB Output is correct
9 Correct 1364 ms 62084 KB Output is correct
10 Correct 911 ms 55360 KB Output is correct
11 Correct 1217 ms 59900 KB Output is correct
12 Correct 1014 ms 57488 KB Output is correct