Submission #1207522

#TimeUsernameProblemLanguageResultExecution timeMemory
1207522mychecksedadEscape Route 2 (JOI24_escape2)C++20
100 / 100
210 ms65312 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> const int N = 3e5+100, M = 1e5+10, K = 52, MX = 30; const ll INF = 1e18; int n, dep[N]; ll t, ANS[N], DEP[N]; vector<array<ll, 3>> go[N]; array<ll, 2> to[N]; vector<pair<int, ll>> g[N], Q[N], QQ[N]; vi T[N]; void solve(){ cin >> n >> t; int id = 1; for(int i = 1; i < n; ++i){ int m; cin >> m; for(int j = 0; j < m; ++j){ int l, r; cin >> l >> r; go[i].pb({l, r, id++}); dep[id - 1] = i; } sort(all(go[i])); vector<array<ll, 3>> v; for(int j = m-1; j >= 0; --j){ if(v.empty()) v.pb(go[i][j]); else{ if(v.back()[1] > go[i][j][1]){ v.pb(go[i][j]); } } } reverse(all(v)); v.swap(go[i]); } for(int i = 1; i + 1 < n; ++i){ for(auto [l, r, ID]: go[i]){ ll w = 0; int pos = lower_bound(all(go[i + 1]), array<ll, 3>{r, -1, -1}) - go[i + 1].begin(); if(pos == go[i + 1].size()) pos = 0, w = go[i + 1][pos][1] + t - r; else w = go[i + 1][pos][1] - r; to[ID] = {w, go[i + 1][pos][2]}; g[to[ID][1]].pb({ID, w}); } } int q; cin >> q; const int C = 600; for(int i = 1; i <= q; ++i){ int l, r; cin >> l >> r; if(go[l].size() >= C) Q[l].pb({r, i}); else QQ[r].pb({l, i}); } vector<int> POS(N); vector<int> root(N); for(auto [l, r, ID]: go[n - 1]) DEP[ID] = 0; for(int i = n - 2; i >= 1; --i){ for(auto [l, r, ID]: go[i]){ DEP[ID] = DEP[to[ID][1]] + to[ID][0]; // cerr << ID << ' ' << DEP[ID] << '\n'; } } ll query_1_2 = INF; int cur_t = 0; for(auto [l, r, ID]: go[1]){ T[cur_t++].pb(ID); POS[ID] = cur_t - 1; root[cur_t - 1] = ID; query_1_2 = min(query_1_2, r - l); } for(auto [l, idx]: QQ[2]) ANS[idx] = query_1_2; for(int i = 2; i < n; ++i){ for(auto [l, r, ID]: go[i]){ int big = -1; for(auto [u, w]: g[ID]){ if(big == -1 || T[POS[u]].size() > T[POS[big]].size()) big = u; } if(big == -1){ T[cur_t++].pb(ID); POS[ID] = cur_t - 1; }else{ POS[ID] = POS[big]; T[POS[ID]].pb(ID); } root[POS[ID]] = ID; for(auto [u, w]: g[ID]){ if(u != big){ for(auto v: T[POS[u]]){ T[POS[ID]].pb(v); POS[v] = POS[ID]; } } } } for(auto [l, idx]: QQ[i + 1]){ ll mn = INF; for(auto [L, R, ID]: go[l]){ mn = min(mn, DEP[ID] - DEP[root[POS[ID]]] + R - L); } ANS[idx] = mn; } } vector<ll> res(n + 1); vector<ll> dist(N); for(int i = 1; i < n; ++i){ if(go[i].size() >= C){ ll mn = INF; for(auto [l, r, ID]: go[i]){ dist[ID] = r - l; mn = min(mn, dist[ID]); } res[i + 1] = mn; for(int j = i + 1; j < n; ++j){ mn = INF; for(auto [l, r, ID]: go[j]){ dist[ID] = INF; for(auto [u, w]: g[ID]){ dist[ID] = min(dist[ID], dist[u] + w); } mn = min(mn, dist[ID]); } res[j + 1] = mn; } for(auto [l, idx]: Q[i]){ ANS[idx] = res[l]; } } } for(int i = 1; i <= q; ++i){ cout << ANS[i] << '\n'; } } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); en; } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\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...