Submission #1153025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153025		jakubmz2	Road Service 2 (JOI24_ho_t5)	C++20	48 / 100	650 ms	204880 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;

int ile[22];
int koszt[MAXN];
int nast[MAXN][22];
int ind[MAXN][22];

bool comp(const pair<int,int> &p1, const pair<int,int> &p2){
    if(p1.second != p2.second){
        return p1.second < p2.second;
    }
    if(p1.first != p2.first){
        return p1.first < p2.first;
    }
    return false;
}

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 last = 0;
int curr = 0;

int jmp(int gdz){
    ll w = 0;
    for(int l = 21; l >= 0; --l){
        if(ind[curr][l] >= gdz) continue;
        w += (1 << l);
        last = ind[curr][l];
        curr = nast[curr][l];
    }
    if(w == (1 << 22) - 1) return -1;
    return w;
}

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});
            }
        }
    }
    //cout << "$\n";
    int nr = 1;
    przedzialy.push_back((d){1000000000, 0});
    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++;
            }
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int l = 1; l <= 21; ++l){
            nast[i][l] = 1e9;
        }
    }
    for(int i = 1; i <= n; ++i){
        nast[i][0] = i;
        ind[i][0] = i;
        for(int j = 1; j <= m; ++j){
            nast[i][0] = max(nast[i][0], przedzialy[kolorek[i][j]].ma);
        }
    }
    for(int l = 1; l <= 21; ++l){
        for(int i = 1; i <= n; ++i){
            nast[i][l] = nast[nast[i][l - 1]][l - 1];
            ind[i][l] = ind[nast[i][l-1]][l-1];
        }
    }
    for(int i = 1; i <= n; ++i){
        cin >> koszt[i];
        if(koszt[i] != 1) exit(0);
    }
    // for(int i = 1; i <= n; ++i){
    //     for(int j = 1; j <= m; ++j){
    //         cout << i << " " << j << " " << "ij\n";
    //         cout << kolorek[i][j] << "\n";
    //     }
    // }
    // for(int i = 1; i < przedzialy.size(); ++i){
    //     cout << i << " " << przedzialy[i].mi << " " << przedzialy[i].ma << " p\n";
    // }
    pi a, b;
    int r;
    for(int i = 0; i < q; ++i){
        cin >> r;
        //cout << r << " r\n";
        if(r == 2){
            cin >> a.first >> a.second >> b.first >> b.second;
            //cout << a.first << " " << a.second << " " << b.first << " " << b.second << " ab\n";
            if(a.first >= b.first){
                swap(a.first, b.first);
                swap(a.second, b.second);
            }
            if(kolorek[a.first][a.second] == kolorek[b.first][b.second]){
                cout << 0 << "\n";
                continue;
            }
            a.first = przedzialy[kolorek[a.first][a.second]].ma;
            b.first = przedzialy[kolorek[b.first][b.second]].mi;
            //cout << a.first << " " << b.first << " first\n";
            if(a.first >= b.first){
                cout << 1 << "\n";
                continue;
            }
            ll w = 0;
            for(ll l = 21; l >= 0; --l){
                if(nast[a.first][l] >= b.first or nast[a.first][l] == -1) continue;
                w += (1 << l);
                //cout << w << " w\n";
                a.first = nast[a.first][l];
            }
            if(w == (1 << 22) - 1) cout << -1 << "\n";
            else cout << w + 2 << "\n";
        }
        else{
            set<int> num;
            for(int j = 0; j < r; ++j){
                cin >> a.first >> a.second;
                num.insert(kolorek[a.first][a.second]);
            }
            vector<pair<int,int>> v;
            int it = 0;
            for(auto u : num){
                v.push_back({przedzialy[u].mi, przedzialy[u].ma});
            }
            if(v.size() == 1){
                cout << 0 << "\n";
                continue;
            }
            // for(auto u : v){
            //     cout << u.first << " " << u.second << " przed\n";
            // }
            sort(v.begin(),v.end(),comp);
            last = v[0].second;
            curr = nast[v[0].second][0];
            ll w = 1;
            while(it < v.size()){
                //cout << curr << " " << last << " wyw\n";
                while(it < v.size() and v[it].first <= last){
                    ++it;
                }
                //cout << v[it].first << " " << v[it].second << " v\n";
                if(it >= v.size()) break;
                int u = jmp(v[it].first);
                //cout << u << " koszt\n";
                if(u == -1){
                    cout << -1 << "\n";
                    w = -1;
                    break;
                }
                w += u;
                //cout << v[it].first << " " << v[it].second << " pr\n";
                //cout << last << " " << curr << " lc\n";
                if(last >= v[it].first){
                    cout << "HUHH\n";
                    exit(0);
                }
                while(it < v.size() and curr > v[it].second){
                    //cout << "#\n";
                    w++;
                    last = max(v[it].second, last);
                    curr = max(curr, nast[v[it].second][0]);
                    ++it;
                    while(it < v.size() and v[it].first <= last){
                        ++it;
                    }
                    //cout << it << " " << v.size() << " czy\n";
                    if(it >= v.size()) break;
                }
                if(it >= v.size()) break;
                //cout << "$\n";
                last = curr;
                curr = nast[curr][0];
                w++;
                while(it < v.size() and v[it].first <= last){
                    ++it;
                }
                if(it >= v.size()) break;
            }
            if(w != -1) cout << w << "\n";
        }
    }
    return 0;
}

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