Longest Park Journey
National Olympiad — National round (2018 season)
Submission name: trip.cpp
Problem summary
Polygonal park paths form a connected cactus: distinct polygons share at most one vertex. Find the longest simple path from A to B.
Input
N M A B, followed by M undirected edges.
Output
The maximum number of edges on a simple A–B path.
Constraints
3 ≤ N ≤ 100,000; A ≠ B. A path exists; the graph is formed by polygon boundaries sharing only vertices.
Worked example
An independently prepared example for this explanation.
Input
10 12 2 5 1 10 10 9 9 8 8 7 7 6 6 5 5 4 4 6 6 10 10 3 3 2 2 1
Output
8
Solution analysis
- Run iterative depth-first search. In a cactus every back edge closes one cycle, and no edge belongs to two cycles. Record the vertices of each cycle in boundary order and mark its edges.
- Replace each cycle by one auxiliary node connected to its vertices; retain bridges. The resulting block tree has a unique A–B route. At a cycle on this route, the entry and exit positions split its boundary into arcs of lengths d and k−d. Use the longer arc.
- In the example the route crosses the four-vertex cycle from 2 to 10, the five-vertex cycle from 10 to 6, and the triangle from 6 to 5. Their longer arcs have lengths 2, 4, and 2, giving 8. No side branch can be visited without repeating its attachment vertex.
Why it works
Every simple path follows the unique route in the block tree: leaving that route forces a repeated articulation vertex. Inside each traversed polygon it must use exactly one of its two boundary arcs. Choices in different polygons share only their route articulation vertices, so choosing each longer arc independently gives a valid simple path and maximizes the total.
Watch out. Do not count an auxiliary-node edge as a real alley. Keep cyclic positions; cycle size alone does not determine the longer arc. Iterative traversal avoids recursion overflow.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m,start,finish;
cin>>n>>m>>start>>finish;
--start;
--finish;
vector<vector<pair<int,int>>>graph(n);
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;
graph[--u].push_back({--v,i});
graph[v].push_back({u,i});
}
vector<int>parent(n,-1),depth(n,-1),edge(n,-1),cursor(n);
vector<bool>cycleEdge(m);
vector<vector<int>>cycles;
vector<int>stack(1,start);
depth[start]=0;
while(!stack.empty()){
int u=stack.back();
if(cursor[u]==int(graph[u].size())){
stack.pop_back();
continue;
}
auto[v,id]=graph[u][cursor[u]++];
if(id==edge[u]){
continue;
}
if(depth[v]==-1){
parent[v]=u;
edge[v]=id;
depth[v]=depth[u]+1;
stack.push_back(v);
}
else if(depth[v]<depth[u]){
vector<int>cycle;
cycleEdge[id]=true;
for(int x=u;x!=v;x=parent[x]){
cycle.push_back(x);
cycleEdge[edge[x]]=true;
}
cycle.push_back(v);
cycles.push_back(cycle);
}
}
vector<vector<pair<int,int>>>tree(n+cycles.size());
for(int u=0;u<n;u++){
for(auto[v,id]:graph[u]){
if(!cycleEdge[id]){
tree[u].push_back({v,0});
}
}
}
for(int i=0;i<int(cycles.size());i++){
for(int j=0;j<int(cycles[i].size());j++){
int v=cycles[i][j];
tree[n+i].push_back({v,j});
tree[v].push_back({n+i,j});
}
}
vector<int>previous(tree.size(),-1),position(tree.size());
stack={start};
previous[start]=start;
for(size_t i=0;i<stack.size();i++){
int u=stack[i];
for(auto[v,j]:tree[u]){
if(previous[v]==-1){
previous[v]=u;
position[v]=j;
stack.push_back(v);
}
}
}
int answer=0;
for(int v=finish;v!=start;){
int u=previous[v];
if(u<n){
answer++;
v=u;
}
else{
// Enter and leave this polygon using its longer boundary arc.
int difference=abs(position[v]-position[u]);
answer+=max(difference,int(cycles[u-n].size())-difference);
v=previous[u];
}
}
cout<<answer<<'\n';
}