Electricity Solution | Round H 2022 - Kick Start 2022

Electricity Solution  KickStart(10pts, 15pts)

Problem

Ben works as an engineer in a city with N$N$ electric junctions. These junctions form a network and can be visualised as a connected graph with N$N$ vertices and N−1$\mathbf{N}-1$ edges. The city is facing a power outage, due to which none of the junctions are receiving electricity, and Ben is in charge of handling the situation.

Each junction has a fixed electric capacity. Ai${\mathbf{A}}_{\mathbf{i}}$ is the electric capacity of the i$i$-th junction. Due to resource constraints, Ben can provide electricity to only one junction, but other junctions can receive electricity depending on their connections and capacities. If the i$i$-th junction receives electricity, then it will also get transmitted to all the junctions directly connected to the i$i$-th junction whose capacity is strictly less than Ai${\mathbf{A}}_{\mathbf{i}}$. Transmission stops if no eligible junction is present. Help Ben determine the maximum number of junctions that can receive electricity.

Input

The first line of the input gives the number of test cases, T$T$. T$T$ test cases follow.
The first line of each test case contains an integer N$N$ which represents the number of junctions in the city.
The next line contains N$N$ integers. The i$i$-th integer is Ai${\mathbf{A}}_{\mathbf{i}}$, which is the electric capacity of the i$i$-th junction.
The next N−1$\mathbf{N}-1$ lines each contain two integers Xi${\mathbf{X}}_{\mathbf{i}}$ and Yi${\mathbf{Y}}_{\mathbf{i}}$, meaning that the junctions Xi${\mathbf{X}}_{\mathbf{i}}$ and Yi${\mathbf{Y}}_{\mathbf{i}}$ are directly connected to each other.

Output

For each test case, output one line containing Case #x$x$: y$y$, where x$x$ is the test case number (starting from 1) and y$y$ is the maximum number of junctions that can receive electricity.

Limits

Time limit: 40 seconds.
Memory limit: 1 GB.
1≤T≤100$1\le \mathbf{T}\le 100$.
1≤Ai≤109$1\le {\mathbf{A}}_{\mathbf{i}}\le {10}^9$, for all i$i$.
1≤Xi,Yi≤N$1\le {\mathbf{X}}_{\mathbf{i}},{\mathbf{Y}}_{\mathbf{i}}\le \mathbf{N}$, for all i$i$.
All the junctions are part of a single connected network.

Test Set 1

1≤N≤103$1\le \mathbf{N}\le {10}^3$.

Test Set 2

For at most 15 cases:
1≤N≤2×105$1\le \mathbf{N}\le 2\times {10}^5$.
For the remaining cases:
1≤N≤103$1\le \mathbf{N}\le {10}^3$.

Sample

Sample Input

2
5
1 2 3 4 3
1 3
2 3
4 3
4 5
6
1 2 3 3 1 4
3 1
3 2
3 4
4 5
1 6

Sample Output

Case #1: 5
Case #2: 3

In Sample Case #1, the optimal solution is to provide electricity to the fourth junction. This will transmit electricity to all the junctions eventually.
If the electricity is provided to the third junction, it will transmit it to the first and second junction, but not to the fourth junction. In that case, only three junctions can finally receive electricity.

In Sample Case #2, the optimal solution is to provide electricity to the third junction. This will transmit it to the first and second junctions. Note that electricity will not be transmitted to the fourth junction, since its capacity is not strictly less than that of the third junction.
If electricity is provided to the sixth junction, it will only be transmitted to the first junction.
If electricity is provided to the fourth junction, it will only be transmitted to the fifth junction.

Solution: 

Brute force Approach: Run DFS and count all the nodes which can be visited but this will get TLE:

#include <bits/stdc++.h>

using namespace std;

#define int            long long int

#define F              first

#define S              second

#define pb             push_back

#define si             set <int>

#define vi             vector <int>

#define pii            pair <int, int>

#define vpi            vector <pii>

#define vpp            vector <pair<int, pii>>

#define mii            map <int, int>

#define mpi            map <pii, int>

#define spi            set <pii>

#define endl           "\n"

#define sz(x)          ((int) x.size())

#define all(p)         p.begin(), p.end()

#define double         long double

#define que_max        priority_queue <int>

#define que_min        priority_queue <int, vi, greater<int>>

#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)

#define print(a)       for(auto x : a) cout << x << " "; cout << endl

#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl

#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)

{

  int x = 1;

  while (b)

  {

    if (b & 1) x *= a;

    a *= a;

    b >>= 1;

  }

  return x;

}

template <typename Arg1>

void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }

template <typename Arg1, typename... Args>

void __f (const char* names, Arg1&& arg1, Args&&... args)

{

  const char* comma = strchr (names + 1, ',');

  cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);

}

const int N = 200005;

void dfs(int src,list<int>*l,vector<int> &vis, vi&v){

    vis[src]=true;

    for(auto nbr:l[src])if(!vis[nbr] && v[src]>v[nbr])dfs(nbr,l,vis,v);

}

void solve(int tc) {

int n;

cin>>n;

vi v(n+1);

for (int i = 1; i <= n; i++)

{

    cin>>v[i];

}

list<int> *l =new list<int>[n+1];

for (int i = 0; i < n-1; i++)

{

    int x,y;

    cin>>x>>y;

    l[x].push_back(y);

    l[y].push_back(x);

}

int ans=0;

for(int i=1; i<=n; i++){

    vector<int>vis(n+1,false);

    dfs(i,l,vis,v);

    int cnt=0;

    for(auto m:vis)if(m==1)cnt++;

    ans=max(ans,cnt);

}

cout<<"Case #"<<tc<<": "<<ans<<endl;

}

int32_t main()

{

  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  clock_t z = clock();

  int t = 1;

  cin >> t;

  int k=1;

  while (t--) solve(k++);

  return 0;

}

Optimized:

We can store the previous results in dp and we need to run DFS only once. Every time we will change our DP and at last, we will find out the max element in the DP for the answer.

#include <bits/stdc++.h>

using namespace std;

#define int            long long int

#define F              first

#define S              second

#define pb             push_back

#define si             set <int>

#define vi             vector <int>

#define pii            pair <int, int>

#define vpi            vector <pii>

#define vpp            vector <pair<int, pii>>

#define mii            map <int, int>

#define mpi            map <pii, int>

#define spi            set <pii>

#define endl           "\n"

#define sz(x)          ((int) x.size())

#define all(p)         p.begin(), p.end()

#define double         long double

#define que_max        priority_queue <int>

#define que_min        priority_queue <int, vi, greater<int>>

#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)

#define print(a)       for(auto x : a) cout << x << " "; cout << endl

#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl

#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)

{

  int x = 1;

  while (b)

  {

    if (b & 1) x *= a;

    a *= a;

    b >>= 1;

  }

  return x;

}

template <typename Arg1>

void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }

template <typename Arg1, typename... Args>

void __f (const char* names, Arg1&& arg1, Args&&... args)

{

  const char* comma = strchr (names + 1, ',');

  cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);

}

const int N = 200005;

void dfs(int src,list<int>*l,vector<int> &vis, vi&v,vi &dp){

    vis[src]=true;

    for(auto nbr:l[src]){

        if(!vis[nbr] && v[src]>v[nbr])

        dfs(nbr,l,vis,v,dp);

        dp[src]+=dp[nbr];

        }

        ++dp[src];

}

void solve(int tc) {

int n;

cin>>n;

vi v(n+1);

for (int i = 1; i <= n; i++)

{

    cin>>v[i];

}

list<int> *l =new list<int>[n+1];

for (int i = 0; i < n-1; i++)

{

    int x,y;

    cin>>x>>y;

    if(v[x]>v[y])l[x].push_back(y);

    else if(v[y]>v[x])l[y].push_back(x);

}

vi visited(n+1,false);

vector<int>dp(n+1,0);

for(int i=1; i<=n; i++){

    if(visited[i])continue;

    dfs(i,l,visited,v,dp);

}

cout<<"Case #"<<tc<<": "<<*max_element(dp.begin(),dp.end())<<endl;

}

int32_t main()

{

  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  clock_t z = clock();

  int t = 1;

  cin >> t;

  int k=1;

  while (t--) solve(k++);

  return 0;

}