Submission #1176222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176222		jakubmz2	Road Service 2 (JOI24_ho_t5)	C++20	0 / 100	3096 ms	220164 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pi pair<int,int>

const int MAXN = 1e6 + 5;

struct d{
    int mi = 1e9;
    int ma = 0;
};

vector<d> przedzialy;
int koszt[MAXN];

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;
}

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;
}

int nxt[MAXN][22][3];

vector<int> jed;
vector<int> dwa;

int p1[MAXN];
int p2[MAXN];

int cl1(int a, int b){
    if(p1[b] < a) return -1;
    else return p1[b];
}

int cl2(int a, int b){
    if(p2[b] < a) return -1;
    else return p2[b];
}


int jmp(int start, int kon){
    int w = 0;
    int curr = start;

    for(int l = 21; l >= 0; --l){
        if(przedzialy[nxt[curr][l][2]].ma < przedzialy[kon].mi){
            curr = nxt[curr][l][2];
            w += (1 << l) + 1;
        }
        else if(przedzialy[nxt[curr][l][1]].ma < przedzialy[kon].mi){
            curr = nxt[curr][l][1];
            w += (1 << l);
        }
        else if(przedzialy[nxt[curr][l][0]].ma < przedzialy[kon].mi){
            curr = nxt[curr][l][0];
            w += (1 << l) - 1;
        }
    }
    int w2 = 1e9;
    if(nxt[curr][0][1] != 0){
        int tc = nxt[curr][0][1];
        if(przedzialy[tc].ma >= przedzialy[kon].mi){
            if(p1[min(przedzialy[kon].ma, przedzialy[tc].ma)] >= przedzialy[kon].mi) w2 = min(w2, w + 2);
            if(p2[min(przedzialy[kon].ma, przedzialy[tc].ma)] >= przedzialy[kon].mi) w2 = min(w2, w + 3);
        }
    }
    if(nxt[curr][0][2] != 0){
        int tc = nxt[curr][0][2];
        if(przedzialy[tc].ma >= przedzialy[kon].mi){
            if(p1[min(przedzialy[kon].ma, przedzialy[tc].ma)] >= przedzialy[kon].mi) w2 = min(w2, w + 3);
            if(p2[min(przedzialy[kon].ma, przedzialy[tc].ma)] >= przedzialy[kon].mi) w2 = min(w2, w + 4);
        }
    }

    return w2;
}

int wiekszy(const int &i1, const int &i2){
    if(i1 == 0) return i2;
    if(i2 == 0) return i1;
    if(przedzialy[i1].ma != przedzialy[i2].ma){
        if(przedzialy[i1].ma > przedzialy[i2].ma) return i1;
        else return i2;
    }
    if(przedzialy[i1].mi != przedzialy[i2].mi){
        if(przedzialy[i1].mi < przedzialy[i2].mi) return i1;
        else return i2;
    }
    if(i1 > i2) return i1;
    else return i2;
}

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 c1 = -1, c2 = -1;
    for(int i = 1; i <= n; ++i){
        cin >> koszt[i];
        if(koszt[i] == 1){
            jed.push_back(i);
            c1 = i;
        }
        else{
            dwa.push_back(i);
            c2 = i;
        }
        p1[i] = c1;
        p2[i] = c2;
    }

    //cout << "$\n";
    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++;
            }
        }
    }
    
    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 = przedzialy.size() - 1; i > 0; --i){
        nxt[i][0][0] = i;
        int w1 = cl1(przedzialy[i].mi, przedzialy[i].ma);
        //cout << i << " " << w1 << " w1\n";
        //cout << przedzialy[i].mi << " " << przedzialy[i].ma << " przedzial\n";
        //cout << p1[przedzialy[1].ma] << " p1\n";
        if(w1 == -1){
            nxt[i][0][1] = 0;
        }
        else{
            int ind = i;
            for(int j = 1; j <= m; ++j){
                if(przedzialy[kolorek[w1][j]].ma > przedzialy[ind].ma){
                    ind = kolorek[w1][j];
                }
                else if(przedzialy[kolorek[w1][j]].ma == przedzialy[ind].ma and przedzialy[kolorek[w1][j]].mi < przedzialy[ind].mi){
                    ind = kolorek[w1][j];
                }
            }
            if(ind == i) nxt[i][0][1] = 0;
            else nxt[i][0][1] = ind;
        }
        int w2 = cl2(przedzialy[i].mi, przedzialy[i].ma);
        if(w2 == -1){
            nxt[i][0][2] = 0;
        }
        else{
            int ind = i;
            for(int j = 1; j <= m; ++j){
                if(przedzialy[kolorek[w2][j]].ma > przedzialy[ind].ma){
                    ind = kolorek[w2][j];
                }
                else if(przedzialy[kolorek[w2][j]].ma == przedzialy[ind].ma and przedzialy[kolorek[w2][j]].mi < przedzialy[ind].mi){
                    ind = kolorek[w2][j];
                }
            }
            if(ind == i) nxt[i][0][2] = 0;
            else nxt[i][0][2] = ind;
        }
        nxt[i][0][2] = wiekszy(nxt[i][0][2], nxt[nxt[i][0][1]][0][1]);
    }

    for(int l = 1; l <= 21; ++l){
        for(int i = 1; i < przedzialy.size(); ++i){
            nxt[i][l][0] = wiekszy(nxt[nxt[i][l-1][1]][l-1][0], nxt[nxt[i][l-1][0]][l-1][1]);
            nxt[i][l][1] = wiekszy(wiekszy(nxt[nxt[i][l-1][1]][l-1][1], nxt[nxt[i][l-1][2]][l-1][0]), nxt[nxt[i][l-1][0]][l-1][2]);
            nxt[i][l][2] = wiekszy(nxt[nxt[i][l-1][1]][l-1][2], nxt[nxt[i][l-1][2]][l-1][1]);
        }
    }

    for(int i = 1; i < przedzialy.size(); ++i){
        int ma = przedzialy[i].mi - 1;
        for(int l = 0; l <= 21; ++l){
            for(int k = 0; k < 3; ++k){
                if(przedzialy[nxt[i][l][k]].ma <= ma) nxt[i][l][k] = 0;
                else if(nxt[i][l][k] != 0) ma = przedzialy[nxt[i][l][k]].ma;
            }
        }
    }
    // cout << nxt[1][0][0] << " " << nxt[1][0][1] << " " << nxt[1][0][2] << " skoki\n";

    // for(int i = 1; i <= n; ++i){
    //     for(int j = 1; j <= m; ++j){
    //         cout << kolorek[i][j] << " ";
    //     }
    //     cout << "\n";
    // }

    pair<int,int> a;
    for(int i = 1; i <= q; ++i){
        int r;
        cin >> r;
        if(r != 2) exit(0);
        cin >> a.first >> a.second;
        int ind1 = kolorek[a.first][a.second];
        cin >> a.first >> a.second;
        int ind2 = kolorek[a.first][a.second];
        if(ind1 == ind2) {
            cout << 0 << "\n";
            continue;
        }
        if(przedzialy[ind1].ma > przedzialy[ind2].ma){
            swap(ind1, ind2);
        }

        if(przedzialy[ind1].ma >= przedzialy[ind2].mi){
            if(p1[przedzialy[ind1].ma] >= przedzialy[ind2].mi and p1[przedzialy[ind1].ma] >= przedzialy[ind1].mi){
                cout << 1 << "\n";
            }
            else cout << 2 << "\n";
            continue;
        }
        int w = jmp(ind1, ind2);
        if(w > 2 * n){
            cout << -1 << "\n";
        }
        else{
            cout << w << "\n";
        }
    }

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 6
• Subtask 3: 0 / 15
• Subtask 4: 0 / 11
• Subtask 5: 0 / 6
• Subtask 6: 0 / 12
• Subtask 7: 0 / 26
• Subtask 8: 0 / 14