제출 #1130724

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1130724		fgdsa	Road Service 2 (JOI24_ho_t5)	C++20	48 / 100	1684 ms	388984 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;
        set<int> tmp;
        for(int j = 0; j < t; ++j){
            int x, y;
            cin >> x >> y;
            tmp.insert(find(x*W + y));
        }

        for(auto j : tmp) punkty.push_back(j);

        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 res = 0;
        int poprzedni = 0;
        int start = punkty[0];
        for(int j = 1; j < punkty.size(); ++j){
            if(start == punkty[j]) continue;

            // cerr << "   " << poprzedni << " " << zakres[punkty[j]].first << '\n';
            if(poprzedni >= zakres[punkty[j]].first){
                poprzedni = min(poprzedni, zakres[punkty[j]].second);
                p = k = poprzedni;
                auto q = query(1, 1, base);
                start = q.second;
                continue;
            }

            // cerr << start << " " << punkty[j] << "\n";
            // cerr << zakres[start].second << ", " << zakres[punkty[j]].first << "\n";

            for(int k = LOG-1; k >= 0; --k){
                // cerr << "   " << k << ": " << zakres[jump[start][k]].second << " " << zakres[punkty[j]].first << '\n';
                if(zakres[jump[start][k]].second < zakres[punkty[j]].first){ 
                    start = jump[start][k], res += (1<<k);
                }
            }   

            // cerr << start << " " << punkty[j] << "\n";
            // cerr << zakres[start].second << ", " << zakres[punkty[j]].first << "\n";

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

            if(zakres[start].second < zakres[punkty[j]].first){
                res = -1;
                break;
            }

            p = k = min(zakres[punkty[j]].second, zakres[start].second);
            auto q = query(1, 1, base);

            if(zakres[punkty[j]].second > zakres[start].second) start = punkty[j];
            if(q.first > zakres[start].second) start = q.second;
            // cerr << start << " " << punkty[j] << "\n";
            // cerr << zakres[start].second << ", " << zakres[punkty[j]].first << "\n";
        }

        cout << res << '\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