This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 2e5 + 5, NODE = 9e5 + 5;
int dist[3][mn], distanc[NODE], leaf[NODE], node[NODE], n, maxNode;
vector<pii> adj[NODE];
bool vis[NODE];
void buildTree (int k, int l, int r) {
maxNode = max(maxNode, k);
if (l == r)
return leaf[l] = k, void();
int mid = (l + r) >> 1;
adj[2 * k].emplace_back(k, 0), buildTree(2 * k, l, mid);
adj[2 * k + 1].emplace_back(k, 0), buildTree(2 * k + 1, mid + 1, r);
}
void buildEdge (int idx, int a, int b, int k, int l, int r) {
if (b < l || r < a) return;
if (a <= l && r <= b)
return adj[k].emplace_back(node[idx], 1), void();
int mid = (l + r) >> 1;
buildEdge(idx, a, b, 2 * k, l, mid);
buildEdge(idx, a, b, 2 * k + 1, mid + 1, r);
}
void bfs (int save, int source) {
for (int i = 1; i <= maxNode; i++)
distanc[i] = INT_MAX, vis[i] = 0;
distanc[leaf[source]] = 0;
deque<int> dq; dq.push_back(leaf[source]);
while (dq.size()) {
int u = dq.front(); dq.pop_front();
if (vis[u]) continue;
vis[u] = 1;
for (pii item : adj[u]) {
int v, w; tie(v, w) = item;
if (distanc[u] + w < distanc[v]) {
distanc[v] = distanc[u] + w;
if (w) dq.push_back(v);
else dq.push_front(v);
}
}
}
for (int i = 1; i <= n; i++)
dist[save][i] = distanc[node[i]];
}
void dijkstra (int save, vector<pii> &sources) {
for (int i = 1; i <= maxNode; i++) distanc[i] = INT_MAX, vis[i] = 0;
priority_queue<pii> pq;
for (pii item : sources) {
int u, dst; tie(u, dst) = item;
pq.emplace(-dst, node[u]);
distanc[node[u]] = dst;
}
while (pq.size()) {
int u = pq.top().second; pq.pop();
if (vis[u]) continue;
vis[u] = 1;
for (pii item : adj[u]) {
int v, w; tie(v, w) = item;
if (distanc[u] + w < distanc[v]) {
distanc[v] = distanc[u] + w;
pq.emplace(-distanc[v], v);
}
}
}
for (int i = 1; i <= n; i++)
dist[save][i] = distanc[node[i]];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
// build segment tree graph
buildTree(1, 1, n);
for (int i = 1; i <= n; i++) {
node[i] = maxNode + i;
adj[node[i]].emplace_back(leaf[i], 0);
}
maxNode += n;
for (int i = 1; i <= n; i++) {
int L, R; cin >> L >> R;
buildEdge(i, L, R, 1, 1, n);
}
// phase 1: bfs from 1 and n
bfs(0, 1), bfs(1, n);
// phase 2: merge paths and continue with dijkstra
vector<pii> sources;
for (int i = 1; i <= n; i++)
if (max(dist[0][i], dist[1][i]) != INT_MAX)
sources.emplace_back(i, dist[0][i] + dist[1][i] - 1);
dijkstra(2, sources);
// answer queries
int q; cin >> q;
while (q--) {
int x; cin >> x;
cout << (dist[2][x] == INT_MAX ? -1 : dist[2][x]) << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |