Submission #1181555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181555		niepamietamhasla	Road Service 2 (JOI24_ho_t5)	C++20	16 / 100	3098 ms	206820 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;

bool comp(const int &i1, const int &i2){
    if(przedzialy[i1].ma != przedzialy[i2].ma) return przedzialy[i1].ma < przedzialy[i2].ma;
    if(przedzialy[i1].mi != przedzialy[i2].mi) return przedzialy[i1].mi < przedzialy[i2].mi;
    return false;
}

bool comp2(const pair<int,int> &p1, const pair<int,int> &p2){
    if(p1.first != p2.first){
        return p1.first < p2.first;
    }
    if(p1.second != p2.second){
        return p1.second > p2.second;
    }
    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;
}


struct trzy{
    int w1;
    int w2;
};

struct dpk{
    int koszt;
    int zaliczony;
    int reach;
};

dpk wiekszy(const dpk &d1, const dpk &d2){
    if(d1.koszt != d2.koszt){
        cout << " huh\n";
        exit(0);
    }
    if(d1.zaliczony != d2.zaliczony){
        return (d1.zaliczony > d2.zaliczony ? d1 : d2);
    }
    if(d1.reach != d2.reach){
        return (d1.reach > d2.reach ? d1 : d2);
    }
    return d1;
}

int koszt[MAXN];
pair<int,int> poprzedni[MAXN];
pair<int,int> nastepny[MAXN];

vector<pair<int,int>> segments;
trzy nxt[MAXN][MAXK];
int start, koniec;
int prefsum[MAXN];
int reach[MAXN];


trzy merge(pair<int,int> curr, int i){
    //nxt[i][j].w1 = max({nxt[nxt[i][j-1].w1][j-1].w2, nxt[nxt[i][j-1].w2][j-1].w1});
    //nxt[i][j].w2 = max({nxt[nxt[i][j-1].w2][j-1].w2, nxt[i][j].w1, nxt[i][j].w2, nxt[reach[nxt[i][j].w1]][j-1].w1});
    trzy odp;
    odp.w1 = max({nxt[curr.first][i-1].w2, nxt[curr.second][i-1].w1});
    odp.w2 = max({nxt[curr.second][i-1].w2, odp.w1, odp.w2, nxt[reach[curr.first]][i-1].w1});
    return odp;
}


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

    vector<int> ind;
    for(int i = 1; i < przedzialy.size(); ++i){
        ind.push_back(i);
    }
    sort(ind.begin(),ind.end(),comp);
    vector<d> nowy;
    vector<int> nowyind;
    nowyind.resize(przedzialy.size());
    nowy.resize(przedzialy.size());
    for(int i = 1; i < przedzialy.size(); ++i){
        nowy[i] = przedzialy[ind[i-1]];
        nowyind[ind[i-1]] = i;
    }
    nowy[0] = przedzialy[0];

    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            kolorek[i][j] = nowyind[kolorek[i][j]];
        }
    }
    przedzialy = nowy;
    nowyind.clear();
    nowy.clear();
    prefsum[0] = 0;
    for(int i = 1; i <= n; ++i){
        reach[i] = i;
        for(int j = 1; j <= m; ++j){
            reach[i] = max(reach[i], przedzialy[kolorek[i][j]].ma);
        }
        if(reach[i] == i){
            prefsum[i]++;
        }
        prefsum[i] += prefsum[i-1];
    }
    }
    
    for(int i = 1; i <= n; ++i){
        nxt[i][0] = {i, max(i, poprzedni[reach[i]].first)};
    }
    for(int j = 1; j <= 19; ++j){
        for(int i = 1; i <= n; ++i){
            nxt[i][j].w1 = max({nxt[nxt[i][j-1].w1][j-1].w2, nxt[nxt[i][j-1].w2][j-1].w1});
            nxt[i][j].w2 = max({nxt[nxt[i][j-1].w2][j-1].w2, nxt[i][j].w1, nxt[i][j].w2, nxt[reach[nxt[i][j].w1]][j-1].w1});
        }
    }

    int r;
    int a, b;
    for(int i = 0; i < q; ++i){
        cin >> r;
        set<int> pkt;
        segments.clear();
        while(r--){
            cin >> a >> b;
            pkt.insert(kolorek[a][b]);
        }
        if(pkt.size() == 1){
            cout << 0 << "\n";
            continue;
        }
        start = n;
        koniec = 0;
        for(auto u : pkt){
            segments.push_back({przedzialy[u].mi, przedzialy[u].ma});
            start = min(start, przedzialy[u].ma);
            koniec = max(koniec, przedzialy[u].mi);
        }
        //cout << start << " " << koniec << " sk\n";
        if(prefsum[koniec - 1] - prefsum[start - 1] > 0){
            cout << -1 << "\n";
            continue;
        }
        sort(segments.begin(),segments.end(),comp2);
        vector<pair<int,int>> dous;
        for(auto u : segments){
            while(dous.size() > 0 and dous.back().second >= u.second){
                dous.pop_back();
            }
            dous.push_back(u);
        }
        bool czy = false;
        segments = dous; 
        // for(auto u : segments){
        //     cout << u.first << " " << u.second << " seg\n";
        // }   
        if(pkt.size() > 1 and segments.size() == 1){
            if(poprzedni[segments[0].second].first >= segments[0].first) cout << 1 << "\n";
            else cout << 2 << "\n";
            continue;
        }
        dpk prev2 = {0, 0, segments[0].second};
        int gdzie = poprzedni[segments[0].second].first;

        int ile = 0;
        int rc;
        //cout << gdzie << " gdz\n";
        if(gdzie >= segments[0].first){
            rc = reach[gdzie];
        }
        else{
            rc = segments[0].second;
        }
        pair<int,int> przedz = segments[0];
        for(int i = 1; i < segments.size(); ++i){
            if(segments[i].first > przedz.second) break;
            pair<int,int> teoretyczny = {segments[i].first, przedz.second};
            if(poprzedni[teoretyczny.second].first >= teoretyczny.first){
                ile = i;
                rc = reach[poprzedni[teoretyczny.second].first];
            }
            else{
                break;
            }
            if(i == segments.size() - 1){
                cout << 1 << "\n";
                czy = true;
                continue;
            }
        }

        dpk prev1 = {1, ile, rc};

        //cout << prev2.koszt << " " << prev2.zaliczony << " " << prev2.reach << " prev2\n";
        //cout << prev1.koszt << " " << prev1.zaliczony << " " << prev1.reach << " prev1\n";

        while(czy == false and prev1.zaliczony < segments.size()-1 and prev2.zaliczony < segments.size()-1){
            //cout << "#\n";
            dpk moz1;
            dpk moz2;
            
            pair<int,int> przedz = {start, prev2.reach};
            int ile = prev2.zaliczony;
            int rc = max(reach[poprzedni[prev2.reach].second], prev2.reach);
            for(int i = ile + 1; i < segments.size(); ++i){
                if(segments[i].first > przedz.second) break;
                pair<int,int> teoretyczny = {segments[i].first, min(przedz.second,segments[i].second)};
                if(poprzedni[teoretyczny.second].second >= teoretyczny.first){
                    ile = i;
                    rc = reach[poprzedni[teoretyczny.second].second];
                }
                else{
                    break;
                }
                if(i == segments.size() - 1){
                    cout << prev2.koszt + 2 << "\n";
                    czy = true;
                    continue;
                }
            }
            if(czy == true) break;
            moz1 = {prev2.koszt + 2, ile, rc};

            ile = prev1.zaliczony;
            rc = max(prev1.reach, reach[poprzedni[prev1.reach].first]);
            przedz = {start, prev1.reach};
            for(int i = ile + 1; i < segments.size(); ++i){
                if(segments[i].first > przedz.second) break;
                pair<int,int> teoretyczny = {segments[i].first, min(przedz.second,segments[i].second)};
                if(poprzedni[teoretyczny.second].first >= teoretyczny.first){
                    ile = i;
                    rc = reach[poprzedni[teoretyczny.second].first];
                }
                else{
                    break;
                }
                if(i == segments.size() - 1){
                    cout << prev1.koszt + 1 << "\n";
                    czy = true;
                    continue;
                }
            }
            if(czy == true){
                break;
            }
            moz2 = {prev1.koszt + 1, ile, rc};


            dpk nowy = wiekszy(moz1, moz2);
            prev2 = prev1;
            prev1 = nowy;
        }
        if(czy == true) continue;
        if(prev2.zaliczony == segments.size()-1){
            cout << prev2.koszt << "\n";
            continue;
        }
        cout << prev1.koszt << "\n";
    }
    return 0;
}

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