Compressed Graph
National Olympiad — Regional round (2025 season)
Submission name: graph.cpp
Problem summary
Each triple (u,l,r) adds edges u→v of weight v−l+1 for every v in [l,r]. Find shortest distances from vertex 1.
Input
N M, then M triples u l r.
Output
N distances in label order; print −1 for unreachable vertices.
Constraints
1 ≤ N ≤ 100000; 1 ≤ M ≤ 200000; 1 ≤ u,l,r ≤ N; l≤r.
Worked example
Official statement example.
Input
10 5 1 1 2 1 8 9 1 7 8 9 3 4 9 3 4
Output
0 2 3 4 -1 -1 1 1 2 -1
Solution analysis
- Build a segment tree whose leaves are the original vertices. A node for [a,b] has edges to its left child of weight 0 and its right child of weight midpoint+1−a. Thus descending from this node to leaf v costs exactly v−a.
- Decompose every interval [l,r] into O(log N) tree nodes. For a selected node beginning at a, add an edge from original vertex u to that node with weight a−l+1. A subsequent descent to leaf v costs v−a, making the total exactly v−l+1. All edges are nonnegative, so run Dijkstra on the resulting sparse graph.
- For group (1,8,9), reaching a canonical node starting at 8 costs 1, and descending to leaf 9 adds 1. Hence it implements the required costs 1 and 2 without listing every interval edge. The sample combines these groups to reach vertices 7 and 8 at distance 1.
Why it works
Every compressed edge is represented by one entry into a canonical covering node and its unique descent to the destination, with exactly the specified weight. Conversely a walk leaving an original vertex enters only a node belonging to one of its groups, and can descend only to a destination inside that group; the descent ends at an original vertex. Thus sparse-graph walks and original walks correspond with equal total weight, and Dijkstra finds the desired distances.
Watch out. Downward edge weights must depend on the left endpoint shift. A zero-weight segment tree alone would incorrectly give every destination the same cost.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every compressed edge is represented by one entry into a canonical covering node and its
// unique descent to the destination, with exactly the specified weight. Conversely a walk leaving an
// original vertex enters only a node belonging to one of its groups, and can descend only to a
// destination inside that group; the descent ends at an original vertex.
#include<functional>
#include<iostream>
#include<limits>
#include<queue>
#include<utility>
#include<vector>
using namespace std;
struct Edge{
int to,weight,next;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector<int>head(5*n+5,-1),node(4*n+5);
vector<Edge>edges;
edges.reserve(4*n+20*m);
auto addEdge=[&](int u,int v,int w){
edges.push_back({v,w,head[u]});
head[u]=static_cast<int>(edges.size())-1;
};
int vertices=n;
function<void(int,int,int)>build=[&](int p,int l,int r){
if(l==r){
node[p]=l;
return;
}
node[p]=++vertices;
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
addEdge(node[p],node[p*2],0);
addEdge(node[p],node[p*2+1],mid+1-l);
};
build(1,1,n);
function<void(int,int,int,int,int,int)>insert=[&](int p,int l,int r,int u,int ql,int qr){
if(ql<=l&&r<=qr){
addEdge(u,node[p],l-ql+1);
return;
}
int mid=(l+r)/2;
if(ql<=mid){
insert(p*2,l,mid,u,ql,qr);
}
if(qr>mid){
insert(p*2+1,mid+1,r,u,ql,qr);
}
};
for(int i=0;i<m;++i){
int u,l,r;
cin>>u>>l>>r;
insert(1,1,n,u,l,r);
}
const long long inf=numeric_limits<long long>::max()/4;
vector<long long>distance(vertices+1,inf);
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>pending;
distance[1]=0;
pending.push({0,1});
while(!pending.empty()){
auto[cost,u]=pending.top();
pending.pop();
if(cost!=distance[u]){
continue;
}
for(int index=head[u];index!=-1;index=edges[index].next){
Edge edge=edges[index];
long long candidate=cost+edge.weight;
if(candidate<distance[edge.to]){
distance[edge.to]=candidate;
pending.push({candidate,edge.to});
}
}
}
for(int v=1;v<=n;++v){
cout<<(distance[v]==inf?-1:distance[v])<<(v==n?'\n':' ');
}
}