#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pi pair<int,int>
struct d{
int mi = 1e9;
int ma = 0;
};
vector<d> przedzialy;
const int MAXN = 1e6 + 5;
const int MAXK = 20;
struct trzy{
int w1;
int w2;
int w3;
int koszt;
};
bool comp(const int &i1, const int &i2){
if(przedzialy[i1].ma != przedzialy[i2].ma) return przedzialy[i1].ma < przedzialy[i2].ma;
if(przedzialy[i1].mi != przedzialy[i2].mi) return przedzialy[i1].mi < przedzialy[i2].mi;
return false;
}
trzy nxt[MAXN][MAXK];
void dfs(int a, int b, int nr, vector<vector<int>> &kolorek, vector<vector<vector<pair<int,int>>>> &graf){
if(kolorek[a][b] != -1) return;
kolorek[a][b] = nr;
przedzialy[nr].mi = min(przedzialy.back().mi, a);
przedzialy[nr].ma = max(przedzialy.back().ma, a);
for(auto u : graf[a][b]){
if(kolorek[u.first][u.second] == -1) dfs(u.first, u.second, nr, kolorek, graf);
}
return;
}
int koszt[MAXN];
pair<int,int> poprzedni[MAXN];
pair<int,int> nastepny[MAXN];
int reach[MAXN];
bool czy = true;
trzy merge(trzy a, int i){
if(a.koszt == 0) return (trzy){nxt[a.w1][i].w1, nxt[a.w1][i].w2, nxt[a.w1][i].w3, 1};
trzy odp;
odp.koszt = a.koszt + (1 << i);
odp.w1 = max(nxt[a.w1][i].w2, nxt[a.w2][i].w1);
odp.w2 = max({nxt[a.w2][i].w2, nxt[a.w1][i].w3, nxt[a.w3][i].w1});
odp.w3 = max(nxt[a.w2][i].w3, nxt[a.w3][i].w2);
return odp;
}
int dpk(int start, int kon){
if(start == kon) return 0;
trzy curr = {start, start, start, 0};
for(int i = 19; i >= 0; --i){
trzy tmp = merge(curr, i);
//cout << i << "\n";
//cout << tmp.w1 << " " << tmp.w2 << " " << tmp.w3 << " " << tmp.koszt << " tmp\n";
//cout << przedzialy[tmp.w2].ma << " " << przedzialy[kon].mi << " pk\n";
if(przedzialy[tmp.w2].ma >= przedzialy[kon].mi) continue;
curr = tmp;
}
//cout << curr.w1 << " " << curr.w2 << " " << curr.w3 << " " << curr.koszt << " po jmp\n";
if(przedzialy[curr.w2].ma < przedzialy[kon].mi){
curr = merge(curr, 0);
}
//cout << curr.w1 << " " << curr.w2 << " " << curr.w3 << " " << curr.koszt << " po merge\n";
if(przedzialy[curr.w2].ma < przedzialy[kon].mi){
return -1;
}
if(poprzedni[min(przedzialy[curr.w2].ma, przedzialy[kon].ma)].first >= przedzialy[kon].mi) return curr.koszt + 1;
else return curr.koszt + 2;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> kolorek;
vector<vector<vector<pair<int,int>>>> graf;
kolorek.resize(n + 1);
graf.resize(n + 1);
for(int i = 0; i <= n; ++i){
kolorek[i].resize(m + 1);
graf[i].resize(m + 1);
}
for(int i = 0; i <= n; ++i){
for(int j = 0; j <= m; ++j){
kolorek[i][j] = -1;
graf[i][j].clear();
}
}
char x;
string s;
for(int i = 1; i <= n; ++i){
cin >> s;
for(int j = 1; j < m; ++j){
x = s[j-1];
//cout << x << " x\n";
if(x == '1') {
graf[i][j].push_back({i,j+1});
graf[i][j+1].push_back({i,j});
}
}
}
//cout << "#\n";
for(int i = 1; i < n; ++i){
cin >> s;
for(int j = 1; j <= m; ++j){
x = s[j-1];
if(x == '1') {
graf[i][j].push_back({i + 1, j});
graf[i+1][j].push_back({i,j});
}
}
}
int nr = 1;
przedzialy.push_back((d){1000000000, 1000000000});
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
if(kolorek[i][j] == -1){
przedzialy.push_back((d){i, i});
dfs(i, j, nr, kolorek, graf);
nr++;
}
}
}
int p1 = -1;
int p2 = -1;
for(int i = 1; i <= n; ++i){
cin >> koszt[i];
if(koszt[i] == 1){
p1 = i;
}
else{
p2 = i;
}
poprzedni[i] = {p1, p2};
//cout << i << " " << poprzedni[i].first << " " << poprzedni[i].second << " poprzednie\n";
}
p1 = n+1;
p2 = n+1;
for(int i = n; i > 0; --i){
if(koszt[i] == 1){
p1 = i;
}
else{
p2 = i;
}
nastepny[i] = {p1, p2};
}
vector<int> ind;
for(int i = 1; i < przedzialy.size(); ++i){
ind.push_back(i);
}
sort(ind.begin(),ind.end(),comp);
vector<d> nowy;
vector<int> nowyind;
nowyind.resize(przedzialy.size());
nowy.resize(przedzialy.size());
for(int i = 1; i < przedzialy.size(); ++i){
nowy[i] = przedzialy[ind[i-1]];
nowyind[ind[i-1]] = i;
}
nowy[0] = przedzialy[0];
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
kolorek[i][j] = nowyind[kolorek[i][j]];
}
}
przedzialy = nowy;
nowyind.clear();
nowy.clear();
for(int i = 1; i <= n; ++i){
reach[i] = -1;
for(int j = 1; j <= m; ++j){
reach[i] = max(reach[i], kolorek[i][j]);
}
}
for(int i = przedzialy.size() - 1; i > 0; --i){
nxt[i][0].w1 = i;
if(poprzedni[przedzialy[i].ma].first >= przedzialy[i].mi){
nxt[i][0].w2 = reach[poprzedni[przedzialy[i].ma].first];
}
else{
nxt[i][0].w2 = i;
}
if(poprzedni[przedzialy[i].ma].second >= przedzialy[i].mi){
nxt[i][0].w3 = reach[poprzedni[przedzialy[i].ma].second];
}
else{
nxt[i][0].w3 = i;
}
nxt[i][0].w3 = max(nxt[i][0].w3, nxt[nxt[i][0].w2][0].w2);
//cout << i << " " << nxt[i][0].w1 << " " << nxt[i][0].w2 << " " << nxt[i][0].w3 << " skoki\n";
}
for(int i = przedzialy.size() - 1; i > 0; --i){
for(int l = 1; l <= 19; ++l){
nxt[i][l].w1 = max(nxt[nxt[i][l-1].w1][l-1].w2, nxt[nxt[i][l-1].w2][l-1].w1);
nxt[i][l].w2 = max({nxt[nxt[i][l-1].w2][l-1].w2, nxt[nxt[i][l-1].w1][l-1].w3, nxt[nxt[i][l-1].w3][l-1].w1});
nxt[i][l].w3 = max(nxt[nxt[i][l-1].w3][l-1].w3, nxt[nxt[i][l-1].w3][l-1].w2);
}
}
// for(int i = 1; i <= n; ++i){
// for(int j = 1; j <= m; ++j){
// cout << kolorek[i][j] << " ";
// }
// cout << "\n";
// }
int r;
int a, b;
for(int i = 0; i < q; ++i){
cin >> r;
if(r != 2) exit(0);
vector<int> pkt;
while(r--){
cin >> a >> b;
pkt.push_back(kolorek[a][b]);
}
sort(pkt.begin(),pkt.end(),comp);
cout << dpk(pkt[0], pkt[1]) << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |