Try to store the ‘node status’ in array instead of map. map giving you an extra cost of log.
@viciousvizard9: I feel you.
@anon55283797: You can also add the following lines inside your main function for fast input/output.
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
WARNING: If you are using this to boost I/O speed, do not use printf and cout together. It will mess up the order in which things are printed.
Can someone tell what is wrong in my code
https://www.codechef.com/viewsolution/34634763
@akshitm16 @galencolin
In your if condition the value will exceed the max limit of integer.So try typecasting to long long…
2 Likes
I am using unordered map. So it will not give an extra cost. It works in O(1).
Can anyone help why. ( float/float) division fails in this solution :CodeChef: Practical coding for everyone
@akshitm16
Hi @sebastian
There were 2 problems in your solution-
- You were using
variable nfor bothnumber of nodesandnumerator. - Overflow while multiplying. Use
lldto for declaration ofa and b arrays.
2 Likes
Still the answer should be 1 2 not 1 1 as 99999/10 is greater.
I knew about second one but the first mistake is blunder… 
1 Like
Don’t worry.
You should always generate some random test cases to debug.
1 Like
Thanks After spending 3 hours I find my mistake which is int overflow in multiplication. 
here is my solution: CodeChef: Practical coding for everyone
1 Like
#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
using namespace std;
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x)
{
cerr << '{';
__print(x.first);
cerr << ',';
__print(x.second);
cerr << '}';
}
template <typename T>
void __print(const T &x)
{
int f = 0;
cerr << '{';
for (auto &i : x)
cerr << (f++ ? "," : ""), __print(i);
cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v)
{
__print(t);
if (sizeof...(v))
cerr << ", ";
_print(v...);
}
#ifndef ONLINE_JUDGE
#define dbg(x...) \
cerr << "[" << #x << "] = ["; \
_print(x)
#else
#define dbg(x...)
#endif
#define endl "\n"
#define FOR(i, a, n) for (ll i = a; i < n; i++)
#define ROF(i, a, n) for (ll i = a; i >= n; i--)
#define all(x) (x).begin(), (x).end()
#define dline cout << "///REACHED///\n";
typedef long long ll;
const ll MOD = 1e+9 + 7;
const ll INF = 0x7f7f7f7f7f7f7f7f;
const int INFi = 0x7f7f7f7f;
const ll MAXN = 4e+5 + 7;
int n, e;
vector<int> g[(int)1e6];
vector<bool> vis(1e6, false);
vector<int> a(1e6, 0), b(1e6, 0);
map<double, int> abyb;
map<double, set<int>> values;
set<int> gans;
void canGetTo(int one, set<int> good, set<int> &ans)
{
// int ctr = 1;
int cur;
// dbg(one, good);
queue<int> q;
q.push(one);
vis[one] = true;
gans.insert(one);
while (!q.empty())
{
// dbg(q.empty());
cur = q.front();
q.pop();
for (auto x : g[cur])
{
// dbg(x);
if (!vis[x] and good.count(x) == 1)
{
// dbg(one, x);
// dbg('H');
vis[x] = true;
gans.insert(x);
q.push(x);
}
}
}
if (gans.size() > ans.size())
{
ans = gans;
}
gans.clear();
}
void solve()
{
cin >> n >> e;
FOR(i, 0, n)
{
cin >> a[i];
}
FOR(i, 0, n)
{
cin >> b[i];
}
FOR(i, 0, n)
{
abyb[(1.0 * a[i]) / (1.0 * b[i])]++;
values[(1.0 * a[i]) / (1.0 * b[i])].insert(i);
}
FOR(i, 0, e)
{
int v1, v2;
cin >> v1 >> v2;
v1--;
v2--;
g[v1].push_back(v2);
g[v2].push_back(v1);
}
set<int> ans;
for (auto points : values[abyb.rbegin()->first])
{
if (!vis[points])
{
canGetTo(points, values[abyb.rbegin()->first], ans);
}
}
cout << ans.size() << endl;
for (auto x : ans)
{
cout << x + 1 << ' ';
}
cout << endl;
a.clear();
b.clear();
for (auto x : g)
{
x.clear();
}
vis.clear();
abyb.clear();
values.clear();
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
indent preformatted text by 4 spaces
I have used BFS to solve the solution but my solution gets TLEd, can some one help me to find why? Thanks in advance.
It’s because you are using a set to keep track of nodes. A simple vector should be enough as we do not care about the order. Insertion time for a set is O(\text{log }n). Generally, it should be fine but this problem seems to have pretty tight constraints.
My Submission
BFS implementation
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin>>t;
while(t–)
{
int n,m;
cin>>n>>m;
long long int a[n+1],b[n+1];
int i;
vectoradj[n+1];
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<=n;i++)
cin>>b[i];
for(i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
long long int num=a[1],deno=b[1];
int vis[n+1]={0};
vectorv[n+1];
for(i=2;i<=n;i++)
{
if(a[i]*deno>b[i]*num)
{
num=a[i];
deno=b[i];
}
}
int max=0;
for(i=1;i<=n;i++)
{
if(a[i]*deno==b[i]*num&&vis[i]==0)
{
queueq;
q.push(i);
vis[i]=1;
while(!q.empty())
{
int x=q.front();
q.pop();
v[i].push_back(x);
for(auto j:adj[x])
{
if(a[j]*deno==b[j]*num&&vis[j]==0)
{
vis[j]=1;
q.push(j);
}
}
}
if(v[i].size()>v[max].size())
max=i;
}
}
cout<<v[max].size()<<endl;
sort(v[max].begin(),v[max].end());
for(auto j: v[max])
cout<<j<<" ";
cout<<endl;
}
return 0;
}
using same concept, with dfs and fast io still getting tle
the king would prefer the number of chosen provinces to be as large as possible.
I somehow thought we had to maximize the population. The DSU tag made me realize. 
I wonder why every problem’s Difficulty is tagged as easy.We can say easy to A B problems but ‘C’ problem comes under Div1.