oj.uz

Submission #129696

# Submission time Handle Problem Language Result Execution time Memory
129696 2019-07-13T04:57:57 Z 김세빈(#3138) 물병 (JOI14_bottle) C++14
0 / 100
 652 ms 55780 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;

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 <pii> 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[t], C[p]);
					}
				}
			}
			x -= dx[i]; y -= dy[i];
		}
		
		for(pii &x: T){
			if(find(x.first) != find(x.second)){
				unite(x.first, x.second);
				K.emplace_back(x.first, x.second, D[x.first] + D[x.second]);
			}
		}
		
		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:89:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0; i<K.size(); i++){
            ~^~~~~~~~~
bottle.cpp:95:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     V[S[i] + E[i] >> 1].push_back(i);
       ~~~~~^~~~~~
bottle.cpp:102:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0; i<K.size(); i++){
            ~^~~~~~~~~
bottle.cpp:106:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
      E[t] = (S[t] + E[t] >> 1) - 1;
              ~~~~~^~~~~~
bottle.cpp:108:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     else S[t] = (S[t] + E[t] >> 1) + 1;
                  ~~~~~^~~~~~
bottle.cpp:114: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:30: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:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", B[i]);
   ~~~~~^~~~~~~~~~~~
bottle.cpp:37: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:80: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 11 ms 5372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 10744 KB Output is correct
2 Incorrect 48 ms 8824 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

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