Submission #1130880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130880		fzyzzz_z	Escape Route 2 (JOI24_escape2)	C++20	54 / 100	3094 ms	107892 KiB

Main

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 1e5 + 10; 
const int L = 17;

int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(0); 
    
    int n; 
    ll t; 
    cin >> n >> t; 

    vector<vector<pair<int, int>>> a(n); 
    vector<vector<int>> xs(n); 
    for (int i = 0; i < n - 1; ++i) {
        int m; 
        cin >> m; 
        a[i].resize(m); 
        for (auto & [x, y]: a[i]) {
            cin >> x >> y; 
        }
        sort(a[i].begin(), a[i].end()); 

        vector<pair<int, int>> b; 
        for (auto [x, y]: a[i]) {
            if (b.size() && b.back().first == x) continue; 
            while (b.size() && b.back().second >= y) b.pop_back(); 
            b.emplace_back(x, y); 
        }
        a[i] = b; 
        for (auto [x, y]: a[i]) {
            xs[i].push_back(x); 
            xs[i + 1].push_back(y); 
        }
    }
    vector<map<int, int>> id(n);
    map<int, pair<int, int>> to; 
    vector<int> day;  
    int ci = 0; 
    for (int i = 0; i < n; ++i) {
        sort(xs[i].begin(), xs[i].end()); 
        xs[i].erase(unique(xs[i].begin(), xs[i].end()), xs[i].end()); 
        for (auto x: xs[i]) {
            day.push_back(i); 
            id[i][x] = ci++; 

            to[ci - 1] = {i, x}; 
        }
    }
    vector<set<int>> ex(n); 
    for (int i = 0; i < n - 1; ++i) {
        for (auto [x, y]: a[i]) {
            ex[i].insert(x); 
        }
    }
    day.push_back(n); 
    ci++; 
    to[ci - 1] = {n, -1}; 

    vector<vector<pair<int, ll>>> g(ci); 
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < a[i].size(); ++j) {
            int tx = a[i][j].first, ty = a[i][j].second; 
            int x = id[i][tx], y = id[i + 1][ty]; 
            g[y].push_back({x, ty - tx});

            if (i == n - 2) {
                g[ci - 1].push_back({y, 0}); 
            } else {
                auto it = ex[i + 1].lower_bound(ty); 
                if (it == ex[i + 1].end()) {
                    int nt = *(ex[i + 1].begin()); 
                    int tt = nt + t - ty; 
                    g[id[i + 1][nt]].push_back({y, tt}); 
                } else if ((*it) != ty) {
                    g[id[i + 1][*it]].push_back({y, (*it) - ty}); 
                }
            }
        }
    }


    const ll inf = 1e18; 

    vector<ll> dt(ci, inf); // distance to last node that is different 
    vector<int> par(ci, -1); 
    function<void(int)> dfs = [&] (int x) {
        for (auto [y, w]: g[x]) {
            assert(day[y] == day[x] || day[y] == day[x] - 1); 
            par[y] = x; 
            dfs(y); 
            if (day[y] != day[x]) {
                if (w < dt[x]) {
                    dt[x] = w; 
                }
            } else {
                if (w + dt[y] < dt[x]) {
                    dt[x] = w + dt[y]; 
                }
            }
        }
        sort(g[x].begin(), g[x].end(), [&](const pair<int, ll> & y, const pair<int, ll> & z) {
            ll vy = day[y.first] != day[x] ? y.second : y.second + dt[y.first]; 
            ll vz = day[z.first] != day[x] ? z.second : z.second + dt[z.first]; 

            return vy < vz; 
        }); 
    }; 
    dfs(ci - 1); 

    int q; 
    cin >> q; 
    vector<vector<pair<int, int>>> qu(n + 1); 
    for (int i = 0; i < q; ++i) {
        int x, y; 
        cin >> x >> y; 
        x--; y--; 
        qu[x].push_back({y, i}); 
    }

    for (auto & v: qu) {
        sort(v.begin(), v.end()); 
    }

    vector<ll> ans(q, inf); 
    vector<int> vis(n + 1, 0); 


    vector<ll> path;
    function<int(int, int, int)> dfs2 = [&] (int x, int top, int exc) {

        assert(n - day[x] == path.size() - 1); 

        // cout << "!!! " << x << ' ' << day[x] << ' ' << top << ' ' <<  ' ' << exc << ' ' << path.back() << '\n'; 


        if (x != ci - 1 && day[par[x]] != day[x]) {

            for (auto [i, qi]: qu[day[x]]) {
                // if (i > top && vis[day[x]]) break;      
                if (i > top && day[x] >= exc) break; 
                ll dist = path.back(); 
                dist -= path[n - i]; 
                // cout << n << ' ' << i << ' ' << path.size() << '\n'; 

                ans[qi] = min(ans[qi], dist); 
            }

            // not vis[x] -> dont go past top 

            // vis[day[x]]++; 
        }

        int mx = day[x]; 
        int cd = -1; 

        for (auto [y, w]: g[x]) {

            if (day[y] == day[x]) path.back() += w; 
            else path.push_back(path.back() + w); 

            int dep = dfs2(y, y == g[x][0].first ? top : day[y], cd == -1 ? (1 << 25) : cd);
            mx = min(mx, dep); 
            if (cd == -1) cd = dep; 

            if (day[y] == day[x]) path.back() -= w; 
            else path.pop_back(); 
        }

        return mx; 
    }; 

    path.push_back(0LL); 
    // path[0] = n 

    dfs2(ci - 1, n, (1 << 25)); 

    for (auto & x: ans) cout << x << "\n"; 


}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 17 / 17
• Subtask 4: 23 / 23
• Subtask 5: 0 / 36
• Subtask 6: 0 / 10