제출 #1349337

#제출 시각아이디문제언어결과실행 시간메모리
1349337alexddEscape Route 2 (JOI24_escape2)C++20
23 / 100
672 ms627428 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int INF = 1e18;

int n,T,cntarb,q;
vector<pair<int,int>> v[100005];
vector<int> id[100005];
int base[100005];

int qle[300005], qri[300005], qrez[300005];

vector<pair<int,int>> qrys[100005];//{jumps, id}
vector<pair<int,int>> con[100005];
int sumr[100005], toroot[100005], depth[100005];
void dfs(int nod)
{
    toroot[depth[nod]] = nod;
    for(auto [jumps, qid]:qrys[nod])
    {
        assert(depth[nod] - jumps >= 0);
        qrez[qid] = min(qrez[qid], base[nod] + sumr[nod] - sumr[toroot[depth[nod] - jumps]]);
    }
    for(auto [adj, w]:con[nod])
    {
        depth[adj] = depth[nod] + 1;
        sumr[adj] = sumr[nod] + w;
        dfs(adj);
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>T;
    for(int i=1;i<n;i++)
    {
        int nr;
        cin>>nr;
        v[i].resize(nr);
        id[i].resize(nr);
        for(int j=0;j<nr;j++)
            cin>>v[i][j].first>>v[i][j].second;
        sort(v[i].begin(), v[i].end());
        for(int j=0;j<nr;j++)
        {
            id[i][j] = ++cntarb;
            base[cntarb] = v[i][j].second - v[i][j].first;
        }
    }
    /*for(int i=1;i<=n;i++)
    {
        cntarb++;
        id[i].push_back(cntarb);
    }*/

    vector<pair<int,int>> tori(cntarb+2, {-1,-1}), tole(cntarb+2, {-1,-1});
    for(int i=1;i+1<n;i++)
    {
        for(int j=0;j<v[i].size();j++)
        {
            int unde = -1, minb = T + 1;
            for(int x=0;x<v[i+1].size();x++)
            {
                if(v[i+1][x].first >= v[i][j].second)
                {
                    if(v[i+1][x].second < minb)
                    {
                        minb = v[i+1][x].second;
                        unde = id[i+1][x];

                        if(i == 1)
                        {
                            //cerr<<minb<<" "<<unde<<" zzz\n";
                        }
                    }
                }
            }
            int cost = 0;
            if(unde == -1)
            {
                assert(!v[i+1].empty());
                unde = id[i+1][0];
                cost = (T - v[i][j].second) + v[i+1][0].second;
            }
            else
            {
                cost = minb - v[i][j].second;
            }
            tori[id[i][j]] = {unde, cost};
        }
    }
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>qle[i]>>qri[i];
        qrez[i] = INF;
    }


    for(int i=1;i<=cntarb;i++)
    {
        if(tori[i].first == -1)
        {
            tori[i].first = cntarb + 1;
            tori[i].second = 0;
        }
        con[tori[i].first].push_back({i, tori[i].second});
    }
    for(int i=1;i<=q;i++)
    {
        for(int j=0;j<v[qle[i]].size();j++)
        {
            qrys[id[qle[i]][j]].push_back({qri[i] - qle[i] - 1, i});
        }
    }

    dfs(cntarb + 1);

    for(int i=1;i<=cntarb+1;i++)
    {
        con[i].clear();
        qrys[i].clear();
    }

    for(int i=1;i<=q;i++)
        cout<<qrez[i]<<"\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...