Pagini recente » Cod sursa (job #2657009) | Profil Ella-chan | Cod sursa (job #472947) | Cod sursa (job #44092) | Cod sursa (job #2495349)
#include <bits/stdc++.h>
#define NMAX 304
#define QMAX 20004
#define pb push_back
#define ft first
#define sd second
using namespace std;
ifstream fin("matrice2.in");
ofstream fout("matrice2.out");
typedef pair <int, int> pairINT;
typedef long long ll;
int n,q,us[NMAX*NMAX], sol[QMAX];
vector <pair <int, pairINT>> edge;
vector <pairINT> waiting[NMAX*NMAX];
set <int> uni[NMAX*NMAX];
void read();
void umerge(int,int,int);
int main(){
read();
for(int i=0,cost,x,y;i<edge.size();++i){
cost=edge[i].ft;
x=edge[i].sd.ft, y=edge[i].sd.sd;
if(us[x] != us[y]){
if(uni[x].size() > uni[y].size())umerge(us[x], us[y], cost);
else umerge(us[y], us[x], cost);
}
}
for(int i=0;i<q;++i)
fout<<sol[i]<<'\n';
return 0;
}
void umerge(int x,int y, int cost){//fill x with y
for(auto it:uni[y]){
for(auto to:waiting[it]){
if(us[to.ft] == x && !sol[to.sd])
sol[to.sd]=cost;
}
us[it]=x;
uni[x].insert(it);
}
uni[y].clear();
}
void read(){// & build graph
int x,y,cost,m[NMAX][NMAX];
fin>>n>>q;
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
fin>>m[i][j];
x=n*(i-1) + j;
us[x]=x;
uni[x].insert(x);
if(i-1){
y=n*(i-2) + j;
cost=min(m[i][j], m[i-1][j]);
edge.pb({cost, {x, y}});
edge.pb({cost, {y, x}});
}
if(j-1){
y=x-1;
cost=min(m[i][j], m[i][j-1]);
edge.pb({cost, {y, x}});
edge.pb({cost, {x, y}});
}
}
}
sort(edge.begin(), edge.end(), greater<pair <int, pairINT>>());
for(int i=0,a,b;i<q;++i){
fin>>a>>b;
x=n*(a-1) + b;
fin>>a>>b;
y=n*(a-1) + b;
waiting[x].pb({y, i});
waiting[y].pb({x, i});
}
}