Submission #986493

#	Time	Username	Problem	Language	Result	Execution time	Memory
986493		boris_mihov	Escape Route 2 (JOI24_escape2)	C++17	100 / 100	245 ms	51024 KiB

Main

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <map>
#include <set>

typedef long long llong;
const int MAXN = 100000 + 10;
const int MAXQ = 300000 + 10;
const int BUCKET_SIZE = 317;
const llong INF = 1e18;

int n, q, t;
struct Flight
{
    int from;
    int to;
    int idx;
};

int cntFlights;
int inTime[MAXN];
llong answer[MAXQ];
llong answer2[MAXN];
std::vector <Flight> v[MAXN];
std::vector <int> minimumTo[MAXN];
std::vector <std::pair <int,int>> g[MAXN];
std::vector <std::pair <int,int>> queries[MAXN];
std::vector <std::pair <int,int>> byLevel[MAXN];
llong toRemove[MAXN];
int flightFrom[MAXN];
int flightTo[MAXN];
int parent[MAXN];
int parEdge[MAXN];
int parEdge2[MAXN];
int dep[MAXN];
llong dist[MAXN];

void buildTree(int node)
{       
    // std::cout << "build tree: " << node << ' ' << dep[node] << ' ' << dist[node] << '\n'; 
    for (const auto &[u, val] : g[node])                
    {                                                                                        
        dep[u] = dep[node] + 1;
        dist[u] = dist[node] + val;
        buildTree(u);
    }
}

void solveDFS(int node)
{
    // std::cout << "here: " << node << ' ' << dep
    toRemove[dep[node]] = dist[node] - parEdge2[node];
    for (const auto &[level, idx] : byLevel[dep[node]])
    {
        answer[idx] = std::min(answer[idx], dist[node] - toRemove[level]);
    }

    for (const auto &[u, val] : g[node])
    {
        solveDFS(u);
    }
}

int specialDep;
llong solveDFS2(int node)
{
    if (dep[node] == specialDep)
    {
        answer2[dep[node]] = std::min(answer2[dep[node]], (llong)parEdge2[node]);
        return dist[node];
    }

    llong minAdd = INF;
    for (const auto &[u, val] : g[node])
    {
        minAdd = std::min(minAdd, solveDFS2(u));
    }

    answer2[dep[node]] = std::min(answer2[dep[node]], minAdd - dist[node] + parEdge2[node]);
    return minAdd;
}

void solve()                                                                                                                                                                                                    
{
    for (int i = 1 ; i < n ; ++i)
    {
        std::sort(v[i].begin(), v[i].end(), [&](auto x, auto y)
        {
            return x.from < y.from || (x.from == y.from && x.to < y.to);
        });
    
        for (int j = 0 ; j < v[i].size() ; ++j)
        {
            v[i][j].idx = ++cntFlights;
            flightFrom[v[i][j].idx] = v[i][j].from;
            flightTo[v[i][j].idx] = v[i][j].to;
        }
    }

    cntFlights++;
    for (const Flight &f : v[n - 1])
    {
        parent[f.idx] = cntFlights;
        parEdge2[f.idx] = f.to - f.from;
        g[cntFlights].push_back({f.idx, f.to - f.from});
    }  

    for (int i = n - 2 ; i >= 1 ; --i)
    {
        minimumTo[i + 1].resize(v[i + 1].size());
        minimumTo[i + 1].back() = v[i + 1][v[i + 1].size() - 1].idx;
        for (int j = (int)v[i + 1].size() - 2 ; j >= 0 ; --j)
        {
            minimumTo[i + 1][j] = minimumTo[i + 1][j + 1];
            if (v[i + 1][j].to < flightTo[minimumTo[i + 1][j]])
            {
                minimumTo[i + 1][j] = v[i + 1][j].idx;
            }
        }

        for (int j = 0 ; j < v[i].size() ; ++j)
        {
            int l = -1, r = v[i + 1].size(), mid;
            while (l < r - 1)
            {
                mid = (l + r) / 2;
                if (v[i + 1][mid].from < v[i][j].to) l = mid;
                else r = mid;
            }

            if (r != v[i + 1].size())
            {
                parent[v[i][j].idx] = minimumTo[i + 1][r];
                parEdge[v[i][j].idx] = flightFrom[minimumTo[i + 1][r]] - v[i][j].from;
                parEdge2[v[i][j].idx] = v[i][j].to - v[i][j].from;
                g[minimumTo[i + 1][r]].push_back({v[i][j].idx, flightFrom[minimumTo[i + 1][r]] - v[i][j].from});
            } else
            {
                parent[v[i][j].idx] = minimumTo[i + 1][0];
                parEdge[v[i][j].idx] = t - v[i][j].from + flightFrom[minimumTo[i + 1][0]];
                parEdge2[v[i][j].idx] = v[i][j].to - v[i][j].from;
                g[minimumTo[i + 1][0]].push_back({v[i][j].idx, t - v[i][j].from + flightFrom[minimumTo[i + 1][0]]});
            }
        }
    }

    for (int i = 1 ; i <= q ; ++i)
    {
        answer[i] = INF;
    }
    
    buildTree(cntFlights);

    for (int l = 1 ; l <= n ; ++l)
    {       
        if (v[l].size() < BUCKET_SIZE)
        {
            for (const auto &[r, idx] : queries[l])
            {
                // std::cout << "add query: " << n - l << ' ' << n - (r - 1) << ' ' << idx << '\n'; 
                byLevel[n - l].push_back({n - (r - 1), idx});
                /*answer[idx] = INF;
                for (const Flight &f : v[l])
                {
                    llong curr = 0;
                    int flightIdx = f.idx;
                    int times = r - l - 1;
                    for (int i = 0 ; i < times ; ++i)
                    {
                        curr += parEdge[flightIdx];
                        flightIdx = parent[flightIdx];
                    }

                    curr += parEdge2[flightIdx];
                    answer[idx] = std::min(answer[idx], curr);
                }*/
            }
        } else
        {
            std::fill(answer2, answer2 + n, INF);
            specialDep = n - l;
            solveDFS2(cntFlights);

            for (const auto &[r, idx] : queries[l])
            {
                answer[idx] = answer2[n - r + 1];
            }
        }
    }

    solveDFS(cntFlights);
}

void print()
{
    for (int i = 1 ; i <= q ; ++i)
    {
        std::cout << answer[i] << '\n';
    }
}

void input()
{
    std::cin >> n >> t;
    for (int i = 1 ; i < n ; ++i)
    {
        int sz;
        std::cin >> sz;
        v[i].resize(sz);

        for (int j = 0 ; j < sz ; ++j)
        {
            std::cin >> v[i][j].from >> v[i][j].to;
        }
    }

    std::cin >> q;
    for (int i = 1 ; i <= q ; ++i)
    {
        int l, r;
        std::cin >> l >> r;
        queries[l].push_back({r, i});
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();
    print();

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:95:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Flight>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for (int j = 0 ; j < v[i].size() ; ++j)
      |                          ~~^~~~~~~~~~~~~
Main.cpp:124:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Flight>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         for (int j = 0 ; j < v[i].size() ; ++j)
      |                          ~~^~~~~~~~~~~~~
Main.cpp:134:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Flight>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |             if (r != v[i + 1].size())
      |                 ~~^~~~~~~~~~~~~~~~~~

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