Submission #1180805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180805		niepamietamhasla	Road Service 2 (JOI24_ho_t5)	C++20	10 / 100	449 ms	240660 KiB

Main

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

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){
    trzy odp;
    if(czy == false){
        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);
        odp.w2 = max(odp.w2, nxt[a.w3][i].w1);
        odp.w3 = max(nxt[a.w2][i].w3, nxt[a.w3][i].w2);
    }
    else{
        odp.w1 = nxt[a.w1][i].w1;
        odp.w2 = nxt[a.w1][i].w2;
        odp.w3 = nxt[a.w1][i].w3;
    }
    return odp;
}

int jmp(int start, pair<int,int> doc, int n){
    if(poprzedni[min(reach[start], doc.second)].first >= doc.first) return 1;
    if(poprzedni[min(reach[start], doc.second)].second >= doc.first) return 2;
    int w = 0;
    czy = true;
    trzy curr = {start, start, start};
    for(int i = 19; i >= 0; --i){
        trzy tmp = merge(curr, i);
        //cout << i << " i\n";
        //cout << curr.w1 << " " << curr.w2 << " " << curr.w3 << " curr\n";
        //cout << tmp.w1 << " " << tmp.w2 << " " << tmp.w3 << " tmp\n";
        if(reach[tmp.w2] >= doc.first or tmp.w2 == curr.w2) continue;
        w += (1 << i);
        czy = false;
        curr = tmp;
    }
    int tmp1 = nxt[curr.w1][0].w2;
    //cout << tmp1 << " za 1\n";
    if(czy == false and tmp1 != n+1 and poprzedni[min(reach[tmp1], doc.second)].first >= doc.first){
        return w + 1;
    }
    else if(czy == false and tmp1 != n+1 and poprzedni[min(reach[tmp1], doc.second)].second >= doc.first){
        return w + 2;
    }
    tmp1 = nxt[curr.w1][0].w3;
    //cout << tmp1 << " za 2\n";
    if(czy == false and tmp1 != n+1 and poprzedni[min(reach[tmp1], doc.second)].first >= doc.first){
        return w + 2;
    }
    //cout << w << " po jmp\n";
    tmp1 = nxt[curr.w2][0].w2;
    //cout << tmp1 << " za 1\n";
    if(tmp1 != n+1 and poprzedni[min(reach[tmp1], doc.second)].first >= doc.first){
        return w + 2;
    }
    else if(tmp1 != n+1 and poprzedni[min(reach[tmp1], doc.second)].second >= doc.first){
        return w + 3;
    }
    tmp1 = nxt[curr.w1][0].w3;
    if(czy == false and tmp1 != n+1 and poprzedni[min(reach[tmp1], doc.second)].second >= doc.first){
        return w + 3;
    }
    tmp1 = nxt[curr.w2][0].w3;
    //cout << tmp1 << " za 2\n";
    if(tmp1 != n+1 and poprzedni[min(reach[tmp1], doc.second)].first >= doc.first){
        return w + 3;
    }
    else if(tmp1 != n+1 and poprzedni[min(reach[tmp1], doc.second)].second >= doc.first){
        return w + 4;
    }
    return 1e9;
}

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};
    }
    
    for(int i = n; i > 0; --i){
        reach[i] = i;
        for(int j = 1; j <= m; ++j){
            reach[i] = max(reach[i], przedzialy[kolorek[i][j]].ma);
        }
        // if(i == 1){
        //     cout << reach[i] << " " << poprzedni[reach[i]].second << " rp\n";    
        // }
        nxt[i][0].w1 = i;
        nxt[i][0].w2 = max(i, poprzedni[reach[i]].first);
        if(poprzedni[reach[i]].first <= i){
            //cout << "#\n";
            nxt[i][0].w2 = 0;
        }
        // if(i == 1){
        //     cout << nxt[i][0].w2 << " w2\n";
        // }
        nxt[i][0].w3 = max(i, poprzedni[reach[i]].second);
        if(poprzedni[reach[i]].second <= i){
            nxt[i][0].w3 = 0;
        }
        nxt[i][0].w3 = max(nxt[i][0].w3, nxt[nxt[i][0].w2][0].w2);
    }

    for(int l = 1; l <= 19; ++l){
        for(int i = 1; i <= n; ++i){
            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].w1][l-1].w3, nxt[nxt[i][l-2].w2][l-1].w2);
            nxt[i][l].w2 = max(nxt[i][l].w2, nxt[nxt[i][l-1].w3][l-1].w1);
            nxt[i][l].w3 = max(nxt[nxt[i][l-1].w3][l-1].w2, nxt[nxt[i][l-1].w2][l-1].w3);
        }
    }
    reach[n+1] = n+1;

    for(int i = 1; i <= n; ++i){
        int prev = -1;
        for(int l = 0; l <= 19; ++l){
            if(nxt[i][l].w1 == 0) nxt[i][l].w1 = n+1;
            if(nxt[i][l].w2 == 0) nxt[i][l].w2 = n+1;
            if(nxt[i][l].w3 == 0) nxt[i][l].w3 = n+1;
            if(nxt[i][l].w2 < prev){
                nxt[i][l].w2 = n+1;
            }
            else if(nxt[i][l].w2 != n+1){
                prev = nxt[i][l].w2;
            }
        }
    }

    //cout << nxt[1][0].w1 << " " << nxt[1][0].w2 << " " << nxt[1][0].w2 << " nxt\n";

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

        //cout << a.first << " " << a.second << " a\n";
        //cout << b.first << " " << b.second << " b\n";
        if(poprzedni[a.second].first >= max(a.first, b.first)){
            cout << 1 << " \n";
            continue;
        }
        else if(poprzedni[a.second].second >= max(a.first, b.first)){
            cout << 2 << " \n";
            continue;
        }

        int w = 1e9;
        if(poprzedni[a.second].first >= a.first){
            int v = jmp(poprzedni[a.second].first, b, n);
            //cout << v << " v\n";
            w = min(w, v + 1);
        }
        if(poprzedni[a.second].second >= a.first){
            w = min(w, jmp(poprzedni[a.second].second, b, n) + 2);
        }
        


        if(w > 2 * n){
            cout << -1 << " \n";
        }
        else{
            cout << w << " \n";
        }
    }


    return 0;
}

• Subtask 1: 10 / 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