Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
  • Work with US
Programmingoneonone
Programmingoneonone

HackerEarth Xsquare And Management problem solution

YASH PAL, 31 July 2024
In this HackerEarth Xsquare And Management problem solution Xsquare has recently started an organisation named HackerEarth. Xsquare has hired N employees having employee ID numbered from 1 to N to work within the organisation. Organisational structure is divided into a number of departments. Each of the N employee is hired to work under exactly one department. All the employees working under the same department are somehow related to each other.
More specifically, organisational structure is represented in the form of a forest containing one or more connected components, where each connected component represents a department and contains the IDs of employees working in that department. A department can be represented in the form of a tree.
Xsquare is busy managing resources for his organisation. Therefore, he cannot participate in the electing the manager for each department.
Can you help him in accomplishing this task ?
Your task is very simple. You have to count the number of ways of selecting manager from each department such that the management level of his organisation is minimum. Since the answer can be large, output it modulo ( 109 + 7 ).
HackerEarth Xsquare And Management problem solution

HackerEarth Xsquare And Management problem solution.

#include <bits/stdc++.h>
using namespace std ;

#define MAXN 500005
#define sc(x) scanf("%d",&x)
#define pb push_back
#define MOD 1000000007
#define ASST(X,A,B) assert(X >= A && X <= B)

int T,N,U,V,M,dist1[MAXN],dist2[MAXN],S[MAXN],E[MAXN],dist,s,e,D[MAXN],visited[MAXN],C[MAXN],ROOT[MAXN],W[MAXN],comp_no,totalN;
vector<int> adj[MAXN] ;
vector<int> comp[MAXN] ;


void dfs(int u){
C[u] = comp_no ;
comp[comp_no].pb(u) ;
for(vector<int> :: iterator it = adj[u].begin() ; it!=adj[u].end() ; ++it){
if(!C[*it]){
dfs(*it) ;
}
}
}

void dfs1(int u){
queue<int> Q;
Q.push(u) ;
stack<int> S ;
visited[u] = 1 ;
while(!Q.empty()){
u = Q.front() ;
S.push(u) ;
Q.pop() ;
for(vector<int> :: iterator it = adj[u].begin(); it != adj[u].end() ; ++it){
if(!visited[*it]){
visited[*it] = 1 ;
Q.push(*it) ;
}
}
}

for(int i=0;i<comp[comp_no].size();i++){
visited[comp[comp_no][i]] = 0 ;
}
dist = s = e = 0 ;
while(!S.empty()){
u = S.top() ;
S.pop() ;
visited[u] = 1 ;
E[u] = u ;
D[u] = 0 ;
int first=u,second=u;
for(vector<int> :: iterator it = adj[u].begin(); it != adj[u].end() ; ++it){
if(visited[*it]){
if(D[first] < D[*it]){
second = first ;
first = *it ;
}else if(D[second] < D[*it]){
second = *it ;
}
}
}
if(dist < (D[first]+D[second]+1)){
dist = D[first]+D[second]+1 ;
s = E[first] ;
e = E[second] ;
}

if(D[first] > D[second]){
D[u] = D[first]+1 ;
E[u] = E[first] ;
}else{
D[u] = D[second]+1;
E[u] = E[second] ;
}

}
}

void dfs2(int u,int cost = 0){
queue<int> Q ;
visited[u] = 1 ;
dist1[u] = cost ;
Q.push(u) ;
while(!Q.empty()){
u = Q.front() ;
Q.pop() ;
for(vector<int> :: iterator it = adj[u].begin() ; it!=adj[u].end() ; ++it){
if(!visited[*it]){
visited[*it] = 1 ;
dist1[*it] = dist1[u] + 1 ;
Q.push(*it) ;
}
}
}
}

void dfs3(int u,int cost = 0){
queue<int> Q ;
visited[u] = 1 ;
dist2[u] = cost ;
Q.push(u) ;
while(!Q.empty()){
u = Q.front() ;
Q.pop() ;
for(vector<int> :: iterator it = adj[u].begin() ; it!=adj[u].end() ; ++it){
if(!visited[*it]){
visited[*it] = 1 ;
dist2[*it] = dist2[u] + 1 ;
Q.push(*it) ;
}
}
}
}
int main(){

// freopen("in11.txt","r",stdin) ;
// freopen("out11.txt","w",stdout) ;
sc(T) ;
ASST(T,1,100000) ;
while(T--){
sc(N) ; sc(M) ;
totalN += N ;
ASST(N,1,500000) ;
ASST(M,0,N-1) ;
for(int i=1;i<=M;i++){
sc(U) ;
sc(V) ;
ASST(U,1,N) ;
ASST(V,1,N) ;
adj[U].pb(V) ;
adj[V].pb(U) ;
}

for(int i=1;i<=N;i++){
visited[i] = 0 ;
D[i] = 0 ;
E[i] = 0 ;
dist1[i] = 0 ;
dist2[i] = 0 ;
C[i] = 0 ;
}
comp_no = 0 ;
for(int i=1;i<=N;i++){
if(!C[i]){
++comp_no ;
dfs(i) ;
}
}

for(int i=1;i<=N;i++)
C[i] = 0 ;
comp_no = 0 ;
for(int i=1;i<=N;i++){
if(!C[i]){
++ comp_no ;
for(int j=0;j<comp[comp_no].size();j++){
visited[comp[comp_no][j]] = 0 ;
}
dfs1(i) ;
for(int j=0;j<comp[comp_no].size();j++){
visited[comp[comp_no][j]] = 0 ;
}
dfs2(s) ;
for(int j=0;j<comp[comp_no].size();j++){
visited[comp[comp_no][j]] = 0 ;
C[comp[comp_no][j]] = comp_no ;
}
dfs3(e) ;
}
}
for(int i=1;i<=comp_no;i++)
ROOT[i] = N , W[i] = 0 ;

for(int i=1;i<=N;i++){
ROOT[C[i]] = min(ROOT[C[i]],max(dist1[i],dist2[i])) ;
}
int ans = 0 ;
for(int i=1;i<=comp_no;i++)
ans = max(ans,ROOT[i]) ;
for(int i=1;i<=N;i++){
if(max(dist1[i],dist2[i]) <= ans){
W[C[i]] ++ ;
}
}
int final_ans = 1 ;
for(int i=1;i<=comp_no;i++){
final_ans = (1LL * final_ans * W[i]) % MOD ;
}
printf("%dn",final_ans) ;
for(int i=1;i<=N;i++){
adj[i].clear() ;
comp[i].clear() ;
}
}
ASST(totalN,1,500000) ;
return 0 ;
}

Second solution

#include <bits/stdc++.h>
#define INF 1000000000
#define M 1000000007
#define lli long long

using namespace std;

vector <int> v[500005];
int dis[2][500005];
int d[500005];
vector < vector<int> > fin;


void dfs(int st)
{
queue <int> q;
vector <int> comp;
comp.clear();

q.push(st);
comp.push_back(st);
d[st] = 0;

while ( !q.empty() ) {
int f = q.front();
q.pop();
for ( int i = 0; i < v[f].size(); i++ ) {
if ( d[v[f][i]] == -1 ) {
d[v[f][i]] = d[f] + 1;
q.push(v[f][i]);
comp.push_back(v[f][i]);
}
}
}

fin.push_back(comp);

int fs, sc, val = -1;

for ( int i = 0; i < comp.size(); i++ ) {
if ( d[comp[i]] > val ) {
val = d[comp[i]];
fs = comp[i];
}
d[comp[i]] = -1;
}

q.push(fs);
d[fs] = 0;

while ( !q.empty() ) {
int f = q.front();
q.pop();
for ( int i = 0; i < v[f].size(); i++ ) {
if ( d[v[f][i]] == -1 ) {
d[v[f][i]] = d[f] + 1;
q.push(v[f][i]);
}
}
}

val = -1;

for ( int i = 0; i < comp.size(); i++ ) {
if ( d[comp[i]] > val ) {
val = d[comp[i]];
sc = comp[i];
}
d[comp[i]] = -1;
}


q.push(fs);
dis[0][fs] = 0;

while ( !q.empty() ) {
int f = q.front();
q.pop();
for ( int i = 0; i < v[f].size(); i++ ) {
if ( dis[0][v[f][i]] == -1 ) {
dis[0][v[f][i]] = dis[0][f] + 1;
q.push(v[f][i]);
}
}
}

q.push(sc);
dis[1][sc] = 0;

while ( !q.empty() ) {
int f = q.front();
q.pop();
for ( int i = 0; i < v[f].size(); i++ ) {
if ( dis[1][v[f][i]] == -1 ) {
dis[1][v[f][i]] = dis[1][f] + 1;
q.push(v[f][i]);
}
}
}
return;
}

// fast input
template<typename T>
inline void fi(T *a)
{
register char c=0;
while (c<33) c=getchar_unlocked();
*a=0;
int tmp = 0;
while (c>33)
{
if ( c == 45 ) tmp = 1;
else *a=*a*10+c-'0';
c=getchar_unlocked();
}
if ( tmp == 1 ) *a = 0-(*a);
}


int main()
{

int n,m,x,y,t;
fi(&t);
assert(t>=1&&t<=100000);
while ( t-- ) {
fi(&n), fi(&m);
assert(n>=1&&n<=500005);
fin.clear();
for ( int i = 1; i <= n; i++ ) {
v[i].clear();
dis[0][i] = dis[1][i] = d[i] = -1;
}
while ( m-- ) {
fi(&x), fi(&y);
v[x].push_back(y);
v[y].push_back(x);
}
for ( int i = 1; i <= n; i++ ) {
if ( dis[0][i] == -1 || dis[1][i] == -1 ) dfs(i);
}
int ans = 0;
for ( int i = 0; i < fin.size(); i++ ) {
int mn = INF;
for ( int j = 0; j < fin[i].size(); j++ ) {
int vert = fin[i][j];
mn = min(mn, max(dis[0][vert],dis[1][vert]));
}
ans = max(ans, mn);
}
lli val = 1;
for ( int i = 0; i < fin.size(); i++ ) {
lli cntt = 0;
for ( int j = 0; j < fin[i].size(); j++ ) {
int vert = fin[i][j];
if ( max(dis[0][vert],dis[1][vert]) <= ans ) cntt++;
}
val = (val * cntt)%M;
}
printf("%lldn", val);
}
return 0;
}
coding problems solutions

Post navigation

Previous post
Next post

Related website

The Computer Science

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes