Traffic Jam Editorial RDC4

general
1

Problem Link:

Practice
Contest-Link

Author - Ayush Tiwari
Tester - Shubham Kushwaha
Editorialist - Ayush Tiwari

Difficulty :

Medium

PREREQUISITES:

Graphs

Problem :

You are given n cities which are connected by m roads. The cities intially has no houses. You have to build either 5 or 6 or 7 houses in each city. There will never be a traffic
jam on road connecting two adjacent city (two city are adjacent if it is directly connected with single road) if sum of number of houses in the cities on both ends of road is odd.

Calculate the number of possible ways to build houses in a cities so there is no jam in any of road in city. Since this number may be large, print it modulo 998244353.

Explanation

First If the graph is not bipartite then answer is zero because If some vertex has an odd number written on it, then we should write even numbers on all adjacent vertices, and vice versa. So it is possible when graph is is bipartite.
if it is, divide it into two parts(means bipartite). The number for each not visited node is 2a+2b, where a is the size of the first part, and b is the size of the second part, because we write 8’s into all vertices of one part, and 7’s or 9’s into all vertices of another part.
so for odd we have two choice and for even we have one choice.
for (int i = 1; i <= n; ++i)
{
if (!visited[i])
{
c1 = 0, c2 = 0;
ans *= bfs(i);
ans *= (pow(2, c1) + pow(2, c2));
ans %= mod;
}

}

Solution

Setter's Solution

#include <bits/stdc++.h>
#include
#include
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ba back
#define ppb pop_back
#define pqb priority_queue
#define eb emplace_back
#define eps 1e-6
#define vll vector
#define pqs priority_queue<int,vll,greater >
#define sz(x) (int((x.size())))
#define all(x) (x).begin(),(x).end()
#define FAST ios_base :: sync_with_stdio (false); cin.tie (NULL)

using namespace std;
typedef long long int ll;
const ll M = 998244353;
const ll N = 2e5 + 5;
const ll inf = 2e18;
ll mod(ll x){ return (x%M);}
ll mod_minus(ll a, ll b){ ll ans= (mod(a)-mod(b)); if(ans<0) ans=mod(ans+M); return ans;}

ll mod_mul(ll a,ll b){ return mod(mod(a)*mod(b));}

ll mod_add(ll a,ll b){ return mod(a+b);}

ll power(ll a,ll n){
if(n==0) return 1;
else if(n==1) return a;
ll R=power(a,n/2)%M;
if(n%2==0) { return mod(mod_mul(R,R)); }

  else {   return mod(mod_mul(mod_mul(R,a),mod(R)));  }
}

ll mod_inv(ll n){ return power(n,M-2);}

// only if M is prime
ll mod_div(ll a,ll b){
ll ans=mod(a); ll b1=power(b,M-2);
ans= mod(mod_mul(ans,b1));
return ans;
}

ll fact_mod(ll n){
vll fact(n+1);
fact[0]=1;
for(ll i=1;i<n+1;i++){
fact[i]=mod_mul(fact[i-1],i);
}
return fact[n];
}
//-------------------------------------
ll nCr_mod(ll n, ll r)
{
if (r == 0 || n==0)
return 1;
ll fac[n + 1];
fac[0] = 1;
for (ll i = 1; i <= n; i++)
fac[i] = (fac[i - 1] * i) % M;

return (fac[n] * mod_inv(fac[r]) % M * mod_inv(fac[n - r]) % M) % M;

}
ll upper_fraction(ll a, ll b)
{
if(a%b==0)
return a/b;
else
return (a/b)+1;
}
bool isInt( double d )
{
double dummy;
return modf( d, &dummy ) == 0.0;
}

vll vis(N);
vector adj(N);

vll colr(N);
ll sz=0;
ll z=0;
bool dfs(ll cur,ll col){
// vis[cur]=1;
colr[cur]=col;

if(col==0)z++;
sz++;
for(ll nb: adj[cur]){
    if(colr[nb]==-1){
       
       if (dfs(nb,!col)==0)return false;
    }
    else { if(colr[nb]==col)return false; }
}
return true;

}
void solve()
{
ll n,m; cin>>n>>m;

z=0; sz=0;

adj.clear(); adj.resize(n+1);
colr.clear(); colr.resize(n+1,-1);
// I use set because of wanted to know number of distinct node which
//is not part of any component
set nodes;
for(ll i=0;i<m;i++){
ll u,v; cin>>u>>v;
adj[u].pb(v);
adj[v].pb(u);
nodes.insert(u); nodes.insert(v);
}

ll res=1;
for(auto i:nodes){
if(adj[i].size()==0)continue;
if(colr[i]==-1){
if (dfs(i,0)){
ll temp=0;

 // for every component 2 ways and every odd node also have 2 ways
      temp=mod_add(power(2,z),power(2,sz-z));
      res=mod_mul(temp,res);
    
        z=0; sz=0;
       }
       else {   cout<<0<<endl; return;} 
     }

}
  // every unique node participate in 3 possiblty
ll adon=power(3,n-nodes.size());

cout<<mod_mul(res,adon)<<endl;
}
int main(){
ll t=1; //cin>>t;
while(t–)
solve();
}

1 Like