In this HackerEarth Little Boruto And Rail Ways problem solution As a present for becoming a Genin, Naruto bought for his son a Lego Train. The little child quickly became addict to the game. He usually spends a lot of time playing with them outside mission times; no wonder why he is good at creating complicated Train Structures.
A Train Structure in Lego is a set of Lego train stations with some Lego roads connecting them. Lego Roads are undirected, that is if you can travel from station(u) to station(v) and the reverse holds too.
After Finishing a structure, Little Boruto tries to improve its design. To do so, he first calculates the designScore of his creation. According to him, the designScore of a structure is the number of train stations from where you can start and return back to using at least 2 Lego roads that are all pairwise different. Then, he will add exactly one Lego road to his structure and re- calculate the designScore and records it. Among all possible choices he has made, he chooses the one which yields the maximum score.
This task is very demanding and Little Boruto never had the chance of trying all possible combinations before bed time. That’s why, he would like you to help him improving the design of his next creations.
HackerEarth Little Boruto And Rail Ways problem solution.
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#define maxn 200001
using namespace std;
vector<int> t[maxn]; // Adjacency list of our graph
set< pair<int,int> > bridges;
bool inCycle[maxn]; // inCycle[i] is true iff vertex_i is in some cycle
bool seen[maxn]; // helper for graph traversal
int low[maxn], entry[maxn];
// low contains the loweset ancestor that can be visited from some vertex
// entry contains the entry time of of vertex_i
// get all bridges of our graph
void getBridges( int s, int parent ) {
static int Time = 0;
seen[s] = true;
entry[s] = low[s] = Time++;
for( int u : t[s] ) {
if( !seen[u] ) {
getBridges(u, s);
low[s] = min(low[s], low[u]);
if( low[u] > entry[s] ) {
bridges.insert(make_pair(u, s));
bridges.insert(make_pair(s, u));
}
} else if( u != parent ){
low[s] = min(low[s], entry[u]);
}
}
}
int heaviness[maxn];
// heaviness is the number of vertexes that are not in a cycle from the root to vertex_i
// traverse our tree and set the heaviness array
void setHeaviness( int s ) {
seen[s] = true;
heaviness[s] += inCycle[s] ? 0 : 1;
for( int u : t[s] ) {
if( seen[u] ) continue;
heaviness[u] = heaviness[s];
setHeaviness(u);
}
}
int main( void ) {
int n, m;
scanf("%i %i", &n, &m);
for( int i = 0; i < m; i++ ) {
int u, v;
scanf("%i %i", &u, &v);
t[v].push_back(u);
t[u].push_back(v);
}
getBridges(1, -1);
// for( auto b : bridges ) {
// printf("[%i %i]\n", b.first, b.second);
// }
fill(seen, seen+n+1, false);
for( int i = 1; i <= n; i++ ) {
// set all vertexes that are in some cycle
if( seen[i] ) continue;
vector<int> comp;
queue<int> Q;
comp.push_back(i);
Q.push(i);
seen[i] = true;
while( !Q.empty() ) {
int u = Q.front(); Q.pop();
for( int v : t[u] ) {
if( bridges.count(make_pair(u, v)) ) continue;
if( !seen[v] ) {
seen[v] = true;
comp.push_back(v);
Q.push(v);
}
}
}
if( comp.size() > 1 ) {
// if this component has more than one vertex
// it means we have some edges that are at least biconnected
// hence in some cycle
for( int u : comp ) inCycle[u] = true;
}
}
// for( int i = 1; i <= n; i++ )
// printf("%i ", inCycle[i]);
// puts("");
fill(heaviness, heaviness+n+1, 0);
fill(seen, seen+n+1, false);
// Now get the diameter of the tree
// the tree is vertex weighted
// if vertex is in some cycle then it has cost 0
// else it has a cost of one
setHeaviness(1);
int s = -1, longest = -1;
for( int i = 1; i <= n; i++ )
if( heaviness[i] > longest ) {
longest = heaviness[i];
s = i;
}
fill(heaviness, heaviness+n+1, 0);
fill(seen, seen+n+1, false);
setHeaviness(s);
// The heaviest node now is one of the endpoints of the diameter
// vertex s is the other endpoint
int designScore = *max_element(heaviness, heaviness+n+1);
for( int i = 1; i <= n; i++ ) {
designScore += inCycle[i] ? 1 : 0;
}
printf("%i\n", designScore);
return 0;
}
Second solution
#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<int> adj[100001];
vector<int> adj2[100001];
int depth[100001];
int P[100001][17];
int seen[100001], now;
vector<pair<int, int>> extra;
int cover[100001];
int ans;
void dfs(int u, int p)
{
seen[u]=++now;
for(auto& v: adj[u]) if(v!=p)
{
if(!seen[v])
{
dfs(v, u);
adj2[u].push_back(v);
adj2[v].push_back(u);
}
else if(seen[v]<seen[u])
extra.push_back({u, v});
}
}
void dfs2(int u, int p)
{
P[u][0]=p;
for(int i=1; i<17; i++)
P[u][i]=P[P[u][i-1]][i-1];
for(auto& v: adj2[u]) if(v!=p)
{
depth[v]=depth[u]+1;
dfs2(v, u);
}
}
int lca(int u, int v)
{
if(depth[u]<depth[v])
swap(u, v);
for(int i=16; i>=0; i--) if(depth[P[u][i]]>=depth[v])
u=P[u][i];
if(u==v)
return u;
for(int i=16; i>=0; i--) if(P[u][i]!=P[v][i])
u=P[u][i], v=P[v][i];
return P[u][0];
}
void dfs3(int u, int p)
{
for(auto& v: adj2[u]) if(v!=p)
{
dfs3(v, u);
cover[u]+=cover[v];
}
}
int dfs4(int u, int p)
{
int c=!cover[u];
vector<int> res;
res.push_back(0);
res.push_back(0);
for(auto& v: adj2[u]) if(v!=p)
res.push_back(dfs4(v, u));
sort(res.rbegin(), res.rend());
ans=max(ans, res[0]+res[1]+c);
return res[0]+c;
}
int main()
{
scanf("%d%d", &N, &M);
assert(1<=N && N<=100000);
assert(1<=M && M<=200000);
set<pair<int, int>> edges;
int a, b;
for(int i=0; i<M; i++)
{
scanf("%d%d", &a, &b);
assert(a!=b);
assert(!edges.count({a, b}));
assert(!edges.count({b, a}));
edges.insert({a, b});
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1, 1);
for(int i=1; i<=N; i++)
assert(seen[i]);
dfs2(1, 1);
for(int i=0; i<(int)extra.size(); i++)
{
int u=extra[i].first;
int v=extra[i].second;
int w=lca(u, v);
cover[u]++;
cover[v]++;
cover[w]--;
if(w!=1)
cover[P[w][0]]--;
}
dfs3(1, 1);
dfs4(1, 1);
for(int i=1; i<=N; i++)
ans+=!!cover[i];
printf("%d\n", ans);
return 0;
}
0 Comments