Submission #1130394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130394		fgdsa	Road Service 2 (JOI24_ho_t5)	C++20	27 / 100	1594 ms	388936 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int H, W;
vector<int> koszt;
vector<int> rodzic;
vector<pair<int, int>> zakres;
vector<pair<int, int>> tree;
vector<pair<int, int>> lazy;
vector<vector<int>> jump;
int base;
int LOG;
int p, k;
pair<int, int> val;

void push(int v, int l, int r){
    if(lazy[v].first > lazy[l].first) lazy[l] = lazy[v];
    if(lazy[v].first > lazy[r].first) lazy[r] = lazy[v];
    
    if(lazy[v].first > tree[l].first) tree[l] = lazy[v];
    if(lazy[v].first > tree[r].first) tree[r] = lazy[v];
}

void add(int v, int a, int b){
    if(a > k || b < p || a > b) return;

    if(p <= a && b <= k){
        if(val.first > tree[v].first) tree[v] = val;
        if(val.first > lazy[v].first) lazy[v] = val;
        return;
    }
    int l = 2*v, r = 2*v+1, mid = (a+b)/2;

    push(v, l, r);

    add(l, a, mid);
    add(r, mid+1, b);

    auto cl = tree[l];
    auto cr = tree[r];

    if(cl.first > cr.first)
        tree[v] = cl;
    else tree[v] = cr;
}

pair<int, int> query(int v, int a, int b){
    if(a > k || b < p || a > b) return {0, 0};
    if(p <= a && b <= k) return tree[v];
    int l = 2*v, r = 2*v+1, mid = (a+b)/2;

    push(v, l, r);

    auto cl = query(l, a, mid);
    auto cr = query(r, mid+1, b);

    if(cl.first > cr.first) return cl;
    return cr;
}

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

    for(auto i : spojne){
        p = zakres[i].first;
        k = zakres[i].second;
        val = {k, i};
        // cerr << i << ": " << p << " " << k << '\n';
        add(1, 1, base);
    }
    // cerr << "\n";

    for(auto i : spojne){
        p = zakres[i].first;
        k = zakres[i].second;
        auto q = query(1, 1, base);
        // cerr << i << ": " << q.first << " " << q.second << '\n';
        jump[i][0] = q.second;
    }
    // cerr << "\n";

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

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

    rodzic.assign((H+3)*(W+3), 0);
    zakres.assign((H+3)*(W+3), {0, 0});
    jump.assign((H+3)*(W+3), vector<int> (LOG));
    tree.assign(2*base, {0, 0});
    lazy.assign(2*base, {0, 0});
    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];
    }

    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){
            // cerr << j << ": " << jump[start][j] << " " << zakres[jump[start][j]].second << '\n';
            if(zakres[jump[start][j]].second < zakres[punkty.back()].first){ 
                start = jump[start][j], res += (1<<j);
            }
        }   

        // cerr << start << ": " << zakres[start].first << " " << zakres[start].second << "\n";
        // cerr << punkty.back() << ": " << zakres[punkty.back()].first << " " << zakres[punkty.back()].second << '\n';
        if(zakres[start].second < zakres[punkty.back()].first){
            start = jump[start][0];
            ++res;
        }
        // cerr << start << "\n";
        if(start != punkty.back()) ++res;

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

    return 0;
}

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