oj.uz

Submission #70993

# Submission time Handle Problem Language Result Execution time Memory
70993 2018-08-24T01:31:14 Z IvanC 물병 (JOI14_bottle) C++17
100 / 100
 1601 ms 239676 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1272 KB Output is correct
2 Correct 8 ms 2948 KB Output is correct
3 Correct 9 ms 3236 KB Output is correct
4 Correct 339 ms 11604 KB Output is correct
5 Correct 326 ms 12972 KB Output is correct
6 Correct 323 ms 14144 KB Output is correct
7 Correct 326 ms 15628 KB Output is correct
8 Correct 286 ms 17412 KB Output is correct
9 Correct 316 ms 18728 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 31484 KB Output is correct
2 Correct 54 ms 31484 KB Output is correct
3 Correct 510 ms 50348 KB Output is correct
4 Correct 650 ms 55544 KB Output is correct
5 Correct 691 ms 61316 KB Output is correct
6 Correct 490 ms 62192 KB Output is correct
7 Correct 647 ms 67708 KB Output is correct
8 Correct 664 ms 73352 KB Output is correct
9 Correct 728 ms 80960 KB Output is correct
10 Correct 561 ms 80960 KB Output is correct
11 Correct 599 ms 83260 KB Output is correct
12 Correct 180 ms 83260 KB Output is correct
13 Correct 210 ms 83260 KB Output is correct
14 Correct 161 ms 88040 KB Output is correct
15 Correct 316 ms 90660 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 90660 KB Output is correct
2 Correct 34 ms 90660 KB Output is correct
3 Correct 313 ms 102040 KB Output is correct
4 Correct 572 ms 107932 KB Output is correct
5 Correct 690 ms 114176 KB Output is correct
6 Correct 723 ms 121616 KB Output is correct
7 Correct 562 ms 121616 KB Output is correct
8 Correct 582 ms 124412 KB Output is correct
9 Correct 193 ms 124412 KB Output is correct
10 Correct 290 ms 124412 KB Output is correct
11 Correct 236 ms 126940 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 903 ms 147716 KB Output is correct
2 Correct 1316 ms 166896 KB Output is correct
3 Correct 453 ms 166896 KB Output is correct
4 Correct 1337 ms 185524 KB Output is correct
5 Correct 1601 ms 207608 KB Output is correct
6 Correct 967 ms 207608 KB Output is correct
7 Correct 556 ms 207608 KB Output is correct
8 Correct 117 ms 207608 KB Output is correct
9 Correct 1443 ms 225996 KB Output is correct
10 Correct 1090 ms 225996 KB Output is correct
11 Correct 1404 ms 239676 KB Output is correct
12 Correct 1248 ms 239676 KB Output is correct