Submission #70993

#	Time	Username	Problem	Language	Result	Execution time	Memory
70993		IvanC	물병 (JOI14_bottle)	C++17	100 / 100	1601 ms	239676 KiB

bottle

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
typedef tuple<int,int,int> trinca;

struct pergunta{
	
	int ini,fim,meio,resp,idx,u,v;

	pergunta(int _ini = 0,int _fim = 0,int _idx = 0,int _u = 0,int _v = 0){
		ini = _ini;
		fim = _fim;
		idx = _idx;
		resp = -1;
		meio = -1;
		u = _u;
		v = _v;
	}

	bool operator<(const pergunta& other)const{
		return meio < other.meio;
	}

};

const int MAXL = 2010;
const int MAXN = 2*1e5 + 10;

const int dx[4] = {1,-1,0,0};
const int dy[4] = {0,0,1,-1};

char entrada[MAXL][MAXL];
int grid[MAXL][MAXL],dist[MAXL][MAXL],H,W,P,Q,pai[MAXN];
int exibe[MAXN];
vector<trinca> Kruskal,MST;
vector<pergunta> D;
queue<ii> bfs;

int find(int x){
	if(x == pai[x]) return x;
	return pai[x] = find(pai[x]);
}

void join(int x,int y){
	x = find(x);
	y = find(y);
	if(x == y) return;
	if(x > y) swap(x,y);
	pai[y] = x;
}

inline int valido(int x,int y){
	return x >= 0 && x < H && y >= 0 && y < W && entrada[x][y] != '#';
}

void reseta_dsu(){
	for(int i = 1;i<=P;i++) pai[i] = i;
}

int main(){

	scanf("%d %d %d %d",&H,&W,&P,&Q);
	for(int i = 0;i<H;i++){
		scanf("%s",entrada[i]);
	}
	for(int i = 1;i<=P;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		x--;y--;
		grid[x][y] = i;
		bfs.push({x,y});
	}
	for(int i = 1;i<=Q;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		pergunta davez(0,P-2,i,u,v);
		D.push_back(davez);
	}

	while(!bfs.empty()){
		int x = bfs.front().first,y = bfs.front().second;
		bfs.pop();
		for(int i = 0;i<4;i++){
			int nx = x + dx[i],ny = y + dy[i];
			if(!valido(nx,ny) || grid[nx][ny] != 0) continue;
			grid[nx][ny] = grid[x][y];
			dist[nx][ny] = dist[x][y] + 1;
			bfs.push({nx,ny});
		}
	}

	for(int i = 0;i<H;i++){
		for(int j = 0;j < W;j++){
			if(!valido(i,j)) continue;
			if(valido(i+1,j) && grid[i][j] != grid[i+1][j]){
				Kruskal.push_back({dist[i][j] + dist[i+1][j], grid[i][j], grid[i+1][j] });
			}
			if(valido(i,j+1) && grid[i][j] != grid[i][j+1]){
				Kruskal.push_back({dist[i][j] + dist[i][j+1],grid[i][j], grid[i][j+1]});
			}
		}
	}

	sort(Kruskal.begin(),Kruskal.end());
	reseta_dsu();
	for(int i = 0;i<Kruskal.size();i++){
		int u = get<1>(Kruskal[i]),v = get<2>(Kruskal[i]);
		if(find(u) != find(v)){
			join(u,v);
			MST.push_back(Kruskal[i]);
		}
	}

	for(int iteracao = 1;iteracao <= 19;iteracao++){

		int meu_ptr = 0;

		for(int i = 0;i<D.size();i++){
			if(D[i].ini > D[i].fim){
				D[i].meio = P;
			}
			else{
				D[i].meio = (D[i].ini + D[i].fim)/2;
			}
		}

		reseta_dsu();
		sort(D.begin(),D.end());

		for(int i = 0;i<D.size();i++){
			if(D[i].meio == P) break;
			while(meu_ptr < MST.size() && meu_ptr <= D[i].meio){
				join(get<1>(MST[meu_ptr]),get<2>(MST[meu_ptr]));
				meu_ptr++;
			}
			if(find(D[i].u) == find(D[i].v)){
				D[i].resp = D[i].meio;
				D[i].fim = D[i].meio - 1;
			}
			else{
				D[i].ini = D[i].meio + 1;
			}
		}

	}

	for(int i = 0;i<D.size();i++) exibe[D[i].idx] = D[i].resp;

	for(int i = 1;i<=Q;i++){
		if(exibe[i] == -1) printf("-1\n");
		else printf("%d\n",get<0>(MST[exibe[i]]));
	}

	return 0;

}

Compilation message (stderr)

bottle.cpp: In function 'int main()':
bottle.cpp:107:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<Kruskal.size();i++){
                ~^~~~~~~~~~~~~~~
bottle.cpp:119:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0;i<D.size();i++){
                 ~^~~~~~~~~
bottle.cpp:131:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0;i<D.size();i++){
                 ~^~~~~~~~~
bottle.cpp:133:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(meu_ptr < MST.size() && meu_ptr <= D[i].meio){
          ~~~~~~~~^~~~~~~~~~~~
bottle.cpp:148:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<D.size();i++) exibe[D[i].idx] = D[i].resp;
                ~^~~~~~~~~
bottle.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d",&H,&W,&P,&Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",entrada[i]);
   ~~~~~^~~~~~~~~~~~~~~~~
bottle.cpp:69: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:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30