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.
#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("%d\n",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("%lld\n", val);
}
return 0;
}
0 Comments