Join Us
TLE
Entering edit mode
// 2. Circuit output
#include <iostream>
#include <algorithm>
const int MOD = 1000000007;
int xorMultiplication(int A, int B, int N) {
int maxProduct = 0;
// Iterate through all possible values of X from 0 to (2^N - 1)
for (int X = 0; X < (1 << N); ++X) {
// Calculate the bitwise XOR of A and X, and B and X
int xorA = A ^ X;
int xorB = B ^ X;
// Calculate the product of (A XOR X) and (B XOR X), taking modulo MOD
int product = ((long long)xorA * xorB) % MOD;
// Update the maximum product if the current product is larger
maxProduct = std::max(maxProduct, product);
}
return maxProduct;
}
int main() {
int A = 4;
int B = 6;
int N = 3;
// Calculate the maximum product using the xorMultiplication function
int result = xorMultiplication(A, B, N);
std::cout << "Maximum Product: " << result << std::endl; // Output: Maximum Product: 35
return 0;
}
Entering edit mode
//compatible warehouses
// time complexity of this code is o(n^3) which is not gonna pass for this case
// because testcse is of order 10^5
#include<bits/stdc++.h>
using namespace std;
int main(){
int warehouse_nodes=6;
int v=warehouse_nodes;
vector<int>warehouse_from={1,6,1,1,4};
vector<int>warehouse_to={6,5,2,4,3};
vector<int> warehouse_weight={4,1,3,2,1};
vector<int> val={2,1,3,1,5,4};
// as it is telling that u should be anssestor of
//v so wwe can make a directed graph
//now can we convert all the usefull variable into zero based
for(int i=0;i<warehouse_nodes-1;i++){
warehouse_from[i]=warehouse_from[i]-1;
warehouse_to[i]=warehouse_to[i]-1;
}
//now we can form a 2d matric to safely find all the distansec between any paiur
//for that we have to come up wiht initiala configuration;
vector<vector<int>> mindis(v,vector<int>(v,1e9));
for(int i=0;i<v;i++){
for(int j=0;j<v;j++){
if(i==j){
mindis[i][j]=0;
}
}
}
vector<vector<int>> adj[warehouse_nodes];
for(int i=0;i<warehouse_nodes-1;i++){
adj[warehouse_from[i]].push_back({warehouse_to[i],warehouse_weight[i]});
mindis[warehouse_from[i]][warehouse_to[i]]=warehouse_weight[i];
}
// applying floyyed warshel algorithm
for(int k=0;k<v;k++){
for(int i=0;i<v;i++){
for(int j=0;j<v;j++){
int u=i;
int v=j;
mindis[u][v]=min(mindis[u][k]+mindis[k][v],mindis[u][v]);
}
}
}
int cnt=0;
// for(int i=0;i<v;i++){
// for(int j=0;j<v;j++){
// if(mindis[i][j]==1e9){
// cout<<i<<" "<<j<< " "<<-1;
// }
// else{
// cout<<i<<" "<<j<< " "<<mindis[i][j];
// }
// cout<<endl;
// }
// }
for(int i=0;i<v;i++){
for(int j=0;j<v;j++){
if(mindis[i][j]<=val[j]&&i!=j){
cnt++;
}
}
}
cout<<cnt;
}
Entering edit mode
COMPATIBLE WAREHOUSES
IT TOOK A LONG TIME TO DEBUG (I GUESS THIS SHOULD BE THE RIGHT APPROACH)
IF I AM WRONG CORRECT ME
#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> adj(200005);
int mod = 1e9 + 7;
int ans = 0;
int dp[200005][22];
int parent[200005][22];
int val1[200005];
int val2[200005];
int dep[200005];
void dfs(int node, int par, int d)
{
dep[node] = d + 1;
parent[node][0] = par;
dp[node][0] = val1[node];
if (parent[node][0] == 0)
dp[node][0] = 1e9;
for (int i = 1; i <= 20; i++)
{
parent[node][i] = parent[parent[node][i - 1]][i - 1];
if (parent[node][i] != 0)
dp[node][i] = dp[node][i - 1] + dp[parent[node][i - 1]][i - 1];
else
dp[node][i] = 1e9;
}
for (auto &ch : adj[node])
{
if (ch != par)
dfs(ch, node, d + 1);
}
}
// find kth ances;
int kth(int node, int k)
{
int val = 0;
for (int i = 21; i >= 0; i--)
{
if (k & (1 << i))
{
val += dp[node][i];
node = parent[node][i];
//cout << "{" << node << " " << val << " } ";
}
}
// cout << endl;
return val;
}
int calc(int node)
{
int ind = -1;
bool fl = 0;
for (int i = 0; i <= 21; i++)
{
int val = dp[node][i];
if (parent[node][i] == 0)
{
if (fl == 0)
{
ind = i;
break;
}
}
if (val2[node] < val)
{
fl = 1;
ind = i;
break;
}
}
//
// cout << "ind" << ind << " ->";
if (ind < 0)
{
// cout<<node<<endl;
return 0;
}
else if (ind == 0)
{
// cout << node << endl;
if (dp[node][ind] <= val2[node])
{
// cout << "{" << node << " " << dp[node][ind] << " " << val2[node] << " "
// << "}" << endl;
return 1;
}
return 0;
}
else
{
int low = 1 << (ind - 1);
int high = 1 << (ind);
if (node == 5)
{
// cout << low << " " << high << endl;
}
int dumans = 0;
int mid = 0;
// cout<<low<<" "<<high<<endl;
while (low <= high)
{
mid = (low + high) / 2;
// cout << mid << endl;
// cout <<"mid"<<mid<<" " <<kth(node, mid)<< " ";
// cout << mid << " " << node << " -";
if (kth(node, mid) <= val2[node])
{
// cout<<"dssd";
dumans = mid;
low = mid + 1;
}
else
high = mid - 1;
}
return dumans;
}
}
void dfs2(int node, int par)
{
ans = (ans % mod + calc(node) % mod) % mod;
//cout << "node" << node << " " << calc(node) << endl;
for (auto &ch : adj[node])
{
if (ch == par)
continue;
else
{
dfs2(ch, node);
}
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> val2[i];
}
int from[n];
int to[n];
int cost[n];
for (int i = 0; i < n - 1; i++)
cin >> from[i];
for (int i = 0; i < n - 1; i++)
cin >> to[i];
for (int i = 0; i < n - 1; i++)
cin >> cost[i];
for (int i = 0; i < n - 1; i++)
{
int u = from[i];
int v = to[i];
int wt = cost[i];
val1[v] = wt;
adj[u].push_back(v);
adj[v].push_back(u);
}
ans = 0;
dfs(1, 0, 1);
dfs2(1, 0);
// for (int i = 1; i <= n; i++)
// {
// cout<<i<<"->";
// for (int j = 0; j <= 20; j++)
// cout << dp[i][j] << " ";
// cout << endl;
// }
//cout << calc(1);
cout << ans << endl;
}
Entering edit mode
Enjoy O(nlog(n)) approach.If you find any flaw in the logic or any test case for which it fails please do comment
#include <iostream>
#include <vector>
using namespace std;
void dfs(int u,vector<vector<pair<int,int>>>& g,vector<bool>& visit,vector<int>& val,vector<int>& dist,long long& pairs){
visit[u]=true;
for(int v=0;v<g[u].size();++v){
int vt=g[u][v].first;
int wt=g[u][v].second;
if(visit[vt])
continue;
int currdist=dist[dist.size()-1]+wt;
int low=0;
int high=dist.size()-1;
int ans=-1;
while(low<=high){
int mid=(low+high)/2;
if(currdist-dist[mid]<=val[vt]){
ans=mid;
high=mid-1;
}
else
low=mid+1;
}
if(ans!=-1)
pairs+=(dist.size()-ans);
dist.push_back(currdist);
dfs(vt,g,visit,val,dist,pairs);
dist.pop_back();
}
}
int main() {
int n;
int e;
std::cin>>n>>e;
vector<vector<pair<int,int>>> g(n+1);
vector<int> val(n+1);
for(int i=0;i<e;++i){
int u;
int v;
int w;
std::cin>>u>>v>>w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
std::cin>>n;
for(int i=1;i<=n;++i)
cin>>val[i];
vector<bool> visit(n+1,false);
vector<int> dist;
dist.push_back(0);
long long pairs=0;
dfs(1,g,visit,val,dist,pairs);
std::cout<<"Number of pairs="<<pairs<<std::endl;
}
Loading Similar Posts
//leveraging binary lifting concept.
#include<bits/stdc++.h>
using namespace std;
void dfs(int node , vector<vector<vector<int>>>&graph , int par , vector<vector<int>>&dp , vector<int>&dist , int curr , int edge){
dp[node][0] = par;
dist[node] = curr + edge;
for(int i = 1 ; i < 20 ; i++){
int x = dp[node][i-1];
if(x == -1) break;
int y = dp[x][i-1];
if( y == -1) break;
else dp[node][i] = y;
}
for(int i = 0 ; i < graph[node].size() ; i++){
if(graph[node][i][0] != par) dfs(graph[node][i][0] , graph , node , dp , dist , dist[node] , graph[node][i][1]);
}
}
int main(){
int n = 6;
//cin >> n;
vector<int>dist(n,0);
vector<int>val = {2,2,8,3,5,4};
vector<vector<vector<int>>>graph(n);
graph[0] = {{5,4} , {3,3}};
graph[5] = {{4,1} , {1,3}};
graph[1] = {{2,1}};
vector<vector<int>>dp(n , vector<int>(20,-1));
dfs(0, graph , -1 , dp , dist , 0 , 0);
int ans = 0;
for(int i = 0 ; i < n ; i++){
int node = i;
int k = 0;
for(int j = 19 ; j >=0 ; j--){
int x = dp[node][j];
if( x != -1){
int dist_btw = dist[i] - dist[x];
if( val[i] >= dist_btw){
k |= (1 << j);
node = x;
}
}
}
ans += k;
}
cout << ans;
}