Cod sursa(job #2476370)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 18 octombrie 2019 18:36:09
Problema Matrice 2 Scor 35
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("matrice2.in");
ofstream fout("matrice2.out");

const int DIM = 307;

int R[DIM * DIM];
int TO[DIM * DIM];

int v[DIM][DIM];

struct Query
{
	int x1, y1, x2, y2, id;
};

int n, m;

int formula(int x, int y)
{
	return (x - 1) * n + y;
}

int sol[DIM * DIM];

int find(int nod)
{
	int i;
	for(i = nod; TO[i] != i; i = TO[i]);
	
	for(; TO[nod] != nod;)
	{
		int y = TO[nod];
		TO[nod] = i;
		nod = y;
	}
	
	return i;
}

void unite(int x, int y)
{
	if(R[x] > R[y])
		TO[y] = x;
	else
		TO[x] = y;
		
	if(R[x] == R[y])
		R[y]++;
}

void solve(int l, int r, vector <Query> q)
{
	if(l > r)
		return ;
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
		{
			R[formula(i, j)] = 1;
			TO[formula(i, j)] = formula(i, j);
		}
	
	vector <Query> st;
	vector <Query> dr;
	
	int mid = (l + r) / 2;
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(v[i][j] >= mid)
			{
				int x = i - 1;
				int y = j;
				
				if(x >= 1 && v[x][y] >= mid)
					unite(find(formula(x, y)), find(formula(i, j)));
				
				x++;
				y--;
				
				if(y >= 1 && v[x][y] >= mid)
					unite(find(formula(x, y)), find(formula(i, j)));
			}
	
	for(auto i : q)
		if(find(formula(i.x1, i.y1)) == find(formula(i.x2, i.y2)))
		{
			sol[i.id] = mid;
			dr.push_back(i);
		}
		else
		{
			st.push_back(i);
		}
	
	if(st.size() != 0)	solve(l, mid - 1, st);
	if(dr.size() != 0)	solve(mid + 1, r, dr);
}

vector <Query> q;

main()
{
	fin >> n >> m;
	
	int mx = 0;
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
		{
			fin >> v[i][j];
			mx = max(mx, v[i][j]);
		}
		
	for(int i = 1; i <= m; i++)
	{
		int x1, y1, x2, y2;
		fin >> x1 >> y1 >> x2 >> y2;
		
		q.push_back(Query{x1, y1, x2, y2, i});
	}
	
	solve(1, mx, q);
	
	for(int i = 1; i <= m; i++)
		fout << sol[i] << '\n';
}