Join Us
Solution has runtime error and TLE
Entering edit mode
// compatible warehouses answer, can anyone verify it
#include <bits/stdc++.h>
using namespace std;
void dfs(int node, vector<int> &dist, vector<int> &ancestors, int bm, vector<vector<int>> adj[], int sum) {
dist[node] = sum;
ancestors[node] = bm;
for (auto c : adj[node]) {
dfs(c[0], dist, ancestors, bm | (1 << node), adj, sum + c[1]); // Corrected 'adj' parameter
}
}
long long int func(int nodes, vector<int> from, vector<int> to, vector<int> weights, vector<int> &val) {
vector<vector<int>> adj[nodes];
for (int i = 0; i < from.size(); i++) { // Use from.size() instead of nodes
adj[from[i] - 1].push_back({to[i] - 1, weights[i]});
}
vector<int> dist(nodes, 0);
int bm = 0;
vector<int> ancestors(nodes, 0);
dfs(0, dist, ancestors, 0, adj, 0);
int count = 0;
for (int i = 0; i < nodes; i++) {
for (int j = 0; j < nodes; j++) {
if ((ancestors[j] & (1 << i)) != 0) { // Change == 1 to != 0
if (dist[j] - dist[i] <= val[j]) {
cout << (i+1) << " "<<(j+1)<<endl;
count++;
}
}
}
}
return count;
}
int main() {
// Example usage
int nodes = 6;
vector<int> from = {1,6,1,1,4};
vector<int> to = {6,5,2,4,3};
vector<int> weights = {4,1,3,2,1};
vector<int> val = {2,1,3,1,5,4};
long long int result = func(nodes, from, to, weights, val);
cout << "Count: " << result << endl;
return 0;
}
Entering edit mode
This is O(nlog(n)) solution.The idea is simple the distances of descendent from the root will be increasing in order as edges are positive thus whenever we land at a node we can always do a binary search to the number of pairs.
#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;
}
Entering edit mode
## woman day mathematics challenge
def getminlength(n, arr):
while len(arr)>1:
min_length = float('inf')
min_index = -1
for i in range(len(arr)-1):
divisor = arr[i+1]
if divisor == 0 or arr[i] == 0:
continue
result = min(arr[i] % divisor, divisor % arr[i])
if result < min_length:
min_length = result
min_index = i
# if min_index == -1:
# break
divisor = arr[min_index+1]
if divisor != 0:
arr[min_index] = min(arr[min_index] % divisor, divisor % arr[min_index])
arr.pop(min_index+1)
return len(arr)
n=4
arr = [1,1,2,3]
result = getminlength(n, arr)
print(result)
Entering edit mode
int fun(vector<int> &arr,int score,int prev,int curr,unordered_map<int,int> &dp,bool valid)
{
if(curr==arr.size())
return score*valid;
int a=0,b=0;
if(arr[curr]-arr[prev]==curr-prev)
{if(dp.find(curr)!=dp.end()) return score+dp[curr];
a=fun(arr,score+arr[curr],curr,curr+1,dp,true);}
b=fun(arr,score,prev,curr+1,dp,valid);
if(a>=b) {dp[curr]=a-score; return a;}
return b;
}
int fun(vector<int> arr)
{
unordered_map<int,int> dp;
int a=0;
for(int i=arr.size()-1;i>=0;i--)
a=max(a,fun(arr,arr[i],i,i+1,dp,false));
return a;
}
Entering edit mode
Compatible houses----
#include<bits/stdc++.h>
using namespace std;
unordered_map<int,vector<pair<int,int>>>graph;
int tot=0;
vector<pair<int,int>>dfs(int node,int par,vector<int>&val)
{
vector<pair<int,int>>head;
for(auto it:graph[node])
{
if(it.first!=par)
{
int weight=it.second;
vector<pair<int,int>>v=dfs(it.first,node,val);
for(auto itr:v)
{
if(itr.second+weight<=val[itr.first-1])tot++;
head.push_back({itr.first,itr.second+weight});
}
}
}
head.push_back({node,0});
return head;
}
int main()
{
int n;
cin>>n;
vector<int>v1(n-1),v2(n-1),weights(n-1),val(n);
for(int i=0;i<n-1;i++)cin>>v1[i];
for(int i=0;i<n-1;i++)cin>>v2[i];
for(int i=0;i<n-1;i++)cin>>weights[i];
for(int i=0;i<n;i++)cin>>val[i];
for(int i=0;i<n-1;i++)
{
graph[v1[i]].push_back({v2[i],weights[i]});
graph[v2[i]].push_back({v1[i],weights[i]});
}
dfs(1,-1,val);
cout<<tot<<endl;
return 0;
}
Loading Similar Posts
can you please tell the constraint on n ?
You have done in O(n^2), But N is 1e5.
So, it gives TLE