Submission #1130344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130344		fgdsa	Road Service 2 (JOI24_ho_t5)	C++20	0 / 100	879 ms	344948 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int H, W;
vector<int> koszt;
vector<int> rodzic;
vector<pair<int, int>> zakres;
vector<vector<int>> jump;
int LOG;

void solve(){
    int t;
    cin >> t;
    
    for(int i = 0; i < t; ++i){
        int x, y;
        cin >> x >> y;
    }
}

int find(int x){
    if(rodzic[x] != x) rodzic[x] = find(rodzic[x]);
    return rodzic[x];
}

void wypisz(){
    for(int i = 1; i <= H; ++i){
        for(int j = 1; j <= W; ++j){
            cerr << i << " " << j << ": " << i*W + j << "\n";
        }
    }
    cerr << "\n\n";

    for(int i = 1; i < (H+3)*(W+3); ++i){
        cerr << i << ": " << rodzic[i] << "\n";
    }
    cerr << "\n\n";

    // for(int i = 1; i < (H+3)*(W+3); ++i){
    //     cerr << i << ": " << zakres[i].first << " " << zakres[i].second << "\n";
    // }
    // cerr << "\n\n";
}

void zrobCosZPrzedzialami(){
    set<int> spojne;
    for(int i = 1; i <= H; ++i){
        for(int j = 1; j <= W; ++j){
            spojne.insert(find(i*W + j));
        }
    }

    vector<int> przedzialy;
    for(auto i : spojne) przedzialy.push_back(i);

    sort(przedzialy.begin(), przedzialy.end(), [&](const int & a, const int & b){
        if(zakres[a].first == zakres[b].first) return zakres[a].second < zakres[b].second;
        return zakres[a].first < zakres[b].first;
    });

    // for(auto i : przedzialy){
    //     cerr << i << ": " << zakres[i].first << " " << zakres[i].second << "\n";
    // }
    // cerr << "\n\n";

    int i = 0;

    for(int j = 0; j < przedzialy.size(); ++j){
        while(i != przedzialy.size() && j + 1 != przedzialy.size() && zakres[przedzialy[j+1]].first > zakres[przedzialy[i]].second){
            // cerr << przedzialy[i] << ": " << zakres[przedzialy[i]].second << ", " << przedzialy[j+1] << ": " << zakres[przedzialy[j+1]].first << "\n";
            jump[przedzialy[i]][0] = przedzialy[j];
            ++i;
        }
    }
    while(i < przedzialy.size()){
        jump[przedzialy[i]][0] = przedzialy.back();
        ++i;
    }
    // cerr << "\n\n";

    // for(auto i : przedzialy){
    //     cerr << i << ": " << jump[i][0] << "\n";
    // }
}

int main(){
    int q;
    cin >> H >> W >> q;
    LOG = log2(H)+2;

    rodzic.assign((H+3)*(W+3), 0);
    zakres.assign((H+3)*(W+3), {0, 0});
    jump.assign((H+3)*(W+3), vector<int> (LOG));
    koszt.assign(H+3, 0);

    for(int i = 1; i <= H; ++i){
        for(int j = 1; j <= W; ++j){
            rodzic[i*W+j] = i*W+j;
            zakres[i*W+j] = {i, i};
        }
    }

    for(int i = 1; i <= H; ++i){
        for(int j = 1; j < W; ++j){
            char c;
            cin >> c;
            if(c == '1'){
                int p1 = find(i*W + j);
                int p2 = find(i*W + j+1);
                rodzic[p1] = p2;
            }
        }
    }

    for(int i = 1; i < H; ++i){
        for(int j = 1; j <= W; ++j){
            char c;
            cin >> c;
            if(c == '1'){
                int p1 = find(i*W + j);
                int p2 = find((i+1)*W + j);
                rodzic[p1] = p2;
                zakres[p2].first = min(zakres[p2].first, zakres[p1].first);
                zakres[p2].second = max(zakres[p2].second, zakres[p1].second);
            }
        }
    }
    
    for(int i = 1; i <= H; ++i){
        cin >> koszt[i];
    }

    // wypisz();
    zrobCosZPrzedzialami();

    for(int i = 1; i < LOG; ++i){
        for(int j = 0; j <= H*W+W; ++j){
            jump[j][i] = jump[jump[j][i-1]][i-1];
        }
    }

    for(int i = 0; i < q; ++i){
        int t;
        cin >> t;

        vector<int> punkty;
        for(int j = 0; j < t; ++j){
            int x, y;
            cin >> x >> y;
            punkty.push_back(find(x*W + y));
        }
            
        sort(punkty.begin(), punkty.end(), [&](const int & a, const int & b){
            if(zakres[a].first == zakres[b].first) return zakres[a].second < zakres[b].second;
            return zakres[a].first < zakres[b].first;
        });

        int start = punkty[0];

        // cerr << start << " " << punkty.back() << "\n";

        if(start == punkty.back()){
            cout << 0 << "\n";
            continue;
        }
        int res = 0;
        for(int j = LOG-1; j >= 0; --j){
            if(zakres[jump[start][j]].second < zakres[punkty.back()].first) start = jump[start][j], res += (1<<j);
        }   

        // cerr << start << "\n";
        ++res;
        start = jump[start][0];
        if(start != punkty.back())++res;

        if(zakres[start].second < zakres[punkty.back()].first){
            cout << -1 << "\n";
        }
        else{
            cout << res << "\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