Corrected it. Thanks for pointing it out.
Can anyone please help out why my code is failing on all TCs
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
void dout(string name, T arg)
{
cerr << "\e[91m" << name << " = " << arg << "\e[39m" << endl;
}
template <typename T1, typename... T2>
void dout(string names, T1 arg, T2... args)
{
cerr << "\e[91m" << names.substr(0, names.find(',')) << " = " << arg << " | \e[39m";
dout(names.substr(names.find(',') + 2), args...);
}
#ifdef LOCAL
#define debug(...) dout(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 42
#endif
template <class Ch, class Tr, class Container>
basic_ostream<Ch, Tr> &operator<<(basic_ostream<Ch, Tr> &os, Container const &x)
{
os << "{ ";
for (auto &y : x)
os << y << " ; ";
return os << "}";
}
template <class X, class Y>
ostream &operator<<(ostream &os, pair<X, Y> const &p)
{
return os << "[ " << p.first << ", " << p.second << "]";
}
typedef pair<long long int, long long int> ii;
typedef vector<long long int> vi;
typedef vector<vector<long long int>> vvi;
typedef vector<pair<long long int, long long int>> vii;
#define pb push_back
// #define mp make_pair
#define ff first
#define ss second
#define all(c) (c).begin(), (c).end()
#define sz(a) ((long long int)(a).size())
#define lli long long int
#define ull unsigned long long int
#define ld long long double
#define ref(i, x, y) for (long long int i = (x); i <= (y); ++i)
#define reb(i, x, y) for (long long int i = (x); i >= (y); --i)
#define trf(c, it) for (auto it = (c).begin(); it != (c).end(); ++it)
#define trb(c, it) for (auto it = (c).end() - 1; it != (c).begin() - 1; --it)
#define tc(t) int t; cin >> t; while (t--)
#define endl '\n'
#define MAX_CAP 200100
#define N 300100
const long long int mod = 1e9 + 7;
const long long int pinf = 9223372036854775807;
const long long int ninf = -9223372036854775807;
lli curr_mod=998244353;
vector<pair<lli,lli>> adj[N];
vector<ii>poss[N];
lli n,k;
lli mark[N];
bool visited[N];
bool visited1[N];
lli children[N];
bool fun(lli curr_a)
{
queue<lli>q;
memset(visited,false,sizeof(visited));
visited[1]=true;
q.push(1);
lli cnt=0;
lli inf=0;
vii pos;
while(!q.empty())
{
lli a=q.front();
inf++;
visited[a]=true;
q.pop();
for(auto i:adj[a])
{
if(visited[i.first])
continue;
if(i.second==0)
{
q.push(i.second);
visited[i.second]=true;
continue;
}
else
pos.push_back({children[i.first],i.first});
}
}
sort(pos.begin(),pos.end(),greater<>());
for(lli x=0;x<pos.size();x++)
{
if(curr_a>0)
{
curr_a--;
continue;
}
inf+=pos[x].first;
}
if(inf>k)
return false;
return true;
}
lli childrenfun(lli a, lli par)
{
if(visited1[a])
return children[a];
visited1[a]=true;
if(adj[a].size()==1)
return children[a]=1;
if(children[a]!=-1)
return children[a];
lli ans=1;
for(auto i:adj[a])
{
if(!visited1[a])
continue;
ans+=childrenfun(i.first, a);
}
return children[a]=ans;
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
tc(t)
{
cin>>n>>k;
vii temp[N];
swap(temp, adj);
for(lli x=0;x<=n;x++)
adj[x].clear();
for(lli x=0;x<n-1;x++)
{
lli u,v,a;
cin>>u>>v>>a;
adj[u].push_back({v,a});
adj[v].push_back({u,a});
}
memset(children,-1,sizeof(children));
memset(visited1,false,sizeof(visited1));
childrenfun(1,-1);
lli start=0,end=n-1,mid;
lli ans=-1;
while(start<=end)
{
mid=(start+end)/2;
if(fun(mid))
ans=mid,end=mid-1;
else start=mid+1;
}
cout<<ans<<endl;
}
return 0;
}
Can anybody give me some testcases where the o/p will be wrong for the solution considering graph as directed?
Can someone tell me why this code fails on last 5 test cases.
https://www.codechef.com/viewsolution/65185878
I need help fixing a bug. I have implemented the following logic
- Start from the root.
- Use BFS to travel the tree.
- If an edge has a weight 1, count the number of nodes in the corresponding subtree using BFS(I have included root of the subtree), and add it to a list(blockable[])
- If edge has weight 0, continue BFS of main tree.
- Sort blockable[] in descending order.
- Keep subtracting elements of blockable from N until N<=K.
- Print the number of elements subtracted.
Every testcase works except the first one. Could someone please tell what is wrong and why.
Link to code: My solution
Consider this test:
STDIN
1
7 3
2 1 1
3 1 1
4 1 0
5 3 1
6 1 1
7 6 1
Expected Output
2
Your Output
-1
The Tree:
It’s exactly the same example I provided before, except that the edges are given in a different way.
Consider these tests:
Input
2
7 4
2 1 0
3 2 0
4 1 0
5 3 1
6 3 0
7 2 1
8 2
2 1 0
3 2 0
4 2 1
5 4 0
6 5 0
7 4 1
8 7 1
Expected Output
-1
-1
Your Output
0
0
The trees:
1 Like
Thanks a lot!
Forgot to store edge weight both ways (u, v & v, u).
why this code is giving tle :->
#include<bits/stdc++.h>
#define ll long long int
using namespace std ;
int dfs(vector&temp,vector<vector<pair<int,int>>>arr,int node,int parent,bool c){
ll sum=0 ;
for(int i=0;i<arr[node].size();i++){
if(arr[node][i].first==parent)continue ;
ll t=dfs(temp,arr,arr[node][i].first,node,(c||arr[node][i].second)) ;
if(arr[node][i].second==1&&c==false)temp.push_back(t) ;
sum+=t ;
}
return sum+1 ;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t ;
cin>>t ;
while(t–){
int n,k ;
cin>>n>>k ;
vector<vector<pair<int,int>>>arr(n+1,vector<pair<int,int>>()) ;
for(int i=0;i<n-1;i++){
int a,b,c ;
cin>>a>>b>>c ;
arr[a].push_back({b,c}) ;
arr[b].push_back({a,c}) ;
}
vectortemp ;
dfs(temp,arr,1,1,false) ;
sort(temp.begin(),temp.end()) ;
reverse(temp.begin(),temp.end()) ;
ll left=n-k ;
if(left<=0){cout<<0<<endl ; continue ; }
ll sum=0 ;
ll ans=0 ;
for(int i=0;i<temp.size();i++){
sum+=temp[i] ;
ans++ ;
if(sum>=left)break ;
}
if(sum>=left)cout<<ans<<endl ;
else cout<<-1<<endl ;
}
return 0 ;
}
Make the graph undirected.
Can some one tell me why my 1st 2 subtasks are are giving wrong ans
Can you explain why are we storing both ways (u,v) and (v,u)?
The question states as:
“Initially, city numbered 1 is infected by a virus. The infection spreads from an infected to an uninfected city only if all the roads present on the shortest path between the cities are unblocked.”
This means we start from city 1 and go down. So the tree should be a directed one.
Am I missing something or interpreting something wrong?
Can you explain why are we storing both ways (u,v) and (v,u)?
The question states as:
“Initially, city numbered 1 is infected by a virus. The infection spreads from an infected to an uninfected city only if all the roads present on the shortest path between the cities are unblocked.”
This means we start from city 1 and go down. So the tree should be a directed one.
Am I missing something or interpreting something wrong?
You are right graph should be directed. But for some input graph can be different if we take graph as directed.
consider the input when we have a edge as 2 → 1 and 3 → 1. If we construct the graph for this input the graph will not be correct. Because edges are given upwards in the input.
1 Like
https://www.codechef.com/viewsolution/72494230
Can Someone pls tell me why is it showing runtime error. In sublime, it is working without any error.