Submission #129710

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
129710	2019-07-13T05:19:50 Z	김세빈(#3138)	물병 (JOI14_bottle)	C++14	Compilation error	0 ms	0 KB

bottle

#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];
		}
	}s
	
	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:70:3: error: 's' was not declared in this scope
  }s
   ^
bottle.cpp:72:12: warning: statement has no effect [-Wunused-value]
  for(i=1; i<=q; i++){
           ~^~~
bottle.cpp:72:20: error: expected ';' before ')' token
  for(i=1; i<=q; i++){
                    ^
bottle.cpp:82:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0; i<K.size(); i++){
            ~^~~~~~~~~
bottle.cpp:88:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     V[S[i] + E[i] >> 1].push_back(i);
       ~~~~~^~~~~~
bottle.cpp:95:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0; i<K.size(); i++){
            ~^~~~~~~~~
bottle.cpp:99:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
      E[t] = (S[t] + E[t] >> 1) - 1;
              ~~~~~^~~~~~
bottle.cpp:101:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     else S[t] = (S[t] + E[t] >> 1) + 1;
                  ~~~~~^~~~~~
bottle.cpp:107: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);
   ~~~~~^~~~~~~~~~~~~~~~