#include <bits/stdc++.h>
#define MAX 200005
#define MOD 998244353
#define INF (ll)(1e18)
#define inf (1987654321)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef complex<long double> cpx;
constexpr long double PI = acos(-1);
int tt, n, m, k, q;
int L[MAX], R[MAX], in[MAX];
int dist1[MAX << 2], dist2[MAX << 2], dist[MAX << 2];
vector<pii> graph[MAX << 2];
vector<int> nodes;
void initGraph(int str, int ed, int node) {
dist1[node] = dist2[node] = n + 1;
if(str == ed) { in[str] = node; return; }
graph[node << 1].push_back({node, 0});
graph[node << 1 | 1].push_back({node, 0});
int mid = str + ed >> 1;
initGraph(str, mid, node << 1);
initGraph(mid + 1, ed, node << 1 | 1);
}
void getRange(int str, int ed, int left, int right, int node) {
if(str > right || ed < left) return;
if(left <= str && ed <= right) {
nodes.push_back(node);
return;
}
int mid = str + ed >> 1;
getRange(str, mid, left, right, node << 1);
getRange(mid + 1, ed, left, right, node << 1 | 1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n; initGraph(1, n, 1);
for(int i = 1; i <= n; ++i) cin >> L[i] >> R[i];
for(int i = 1; i <= n; ++i) {
nodes.clear(); getRange(1, n, L[i], R[i], 1);
for(auto v : nodes) graph[v].push_back({in[i], 1});
}
deque<pii> dq;
dq.push_back({in[1], 0});
while(!dq.empty()) {
int cur = dq.front().first;
int d = dq.front().second;
dq.pop_front();
if(dist1[cur] != n + 1) continue;
dist1[cur] = d;
for(auto [v, w] : graph[cur]) {
if(w == 0) dq.push_front({v, d});
else dq.push_back({v, d + 1});
}
}
dq.push_back({in[n], 0});
while(!dq.empty()) {
int cur = dq.front().first;
int d = dq.front().second;
dq.pop_front();
if(dist2[cur] != n + 1) continue;
dist2[cur] = d;
for(auto [v, w] : graph[cur]) {
if(w == 0) dq.push_front({v, d});
else dq.push_back({v, d + 1});
}
}
for(int i = 1; i <= n; ++i) {
cout << i << " : ";
for(auto [v, w] : graph[in[i]]) cout << "(" << v << ", " << w << ") ";
cout << endl;
}
for(int i = 1; i <= 4 * n; ++i) dist[i] = dist1[i] + dist2[i];
priority_queue<pii> pq;
for(int i = 1; i <= 4 * n; ++i) pq.push({-dist[i], i});
while(!pq.empty()) {
int d = -pq.top().first;
int cur = pq.top().second;
pq.pop();
if(dist[cur] < d) continue;
for(auto [v, w] : graph[cur]) {
if(dist[v] > dist[cur] + w) {
dist[v] = dist[cur] + w;
pq.push({-dist[v], v});
}
}
}
cin >> q;
while(q--) {
int x; cin >> x;
if(dist[in[x]] > n) cout << -1 << '\n';
else cout << dist[in[x]] << '\n';
}
return 0;
}
Compilation message
passport.cpp: In function 'void initGraph(int, int, int)':
passport.cpp:28:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
28 | int mid = str + ed >> 1;
| ~~~~^~~~
passport.cpp: In function 'void getRange(int, int, int, int, int)':
passport.cpp:39:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
39 | int mid = str + ed >> 1;
| ~~~~^~~~
passport.cpp: In function 'int main()':
passport.cpp:66:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
66 | for(auto [v, w] : graph[cur]) {
| ^
passport.cpp:81:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
81 | for(auto [v, w] : graph[cur]) {
| ^
passport.cpp:89:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
89 | for(auto [v, w] : graph[in[i]]) cout << "(" << v << ", " << w << ") ";
| ^
passport.cpp:103:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
103 | for(auto [v, w] : graph[cur]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
27224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
27228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
27228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
27228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
27224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
