web_developer's blog

By web_developer, history, 3 years ago, In English

Hello Codeforces, I need help with this problem

My sol. -> I've written recursive solution and it gives TLE on tc 20

Now, I want to optimize this... How can I? Plz help.

Thanks!!

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By web_developer, history, 3 years ago, In English

Hello codeforces, I was solving this problem and I ended up with below solution, but this solution doesn't seem to work on test case 5, can you help me find where I've gone wrong and I don't want to see the editorial until I don't get my approach accepted. It's a simple bfs if you've got time to see it. Please help..I wasted so much time on this.

My approach: Firstly, I am making a bfs call from every node from 1 to n and finding their neighbours or second-neighbours and so on..so that minimum s towns having a different type of goods and for finding cost I am using a level array. Suppose I am starting bfs from node-2 then level of this node I am taking 0 and its neighbours level 1 and so on, so it gives me nearest s towns who has to produce a different type of goods and for answer, I am summing their cost. Hope you understood my approach.

Code

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define mod 1000000007
 
vector<int> adj[N];
vector<bool> visited(N, false);
unordered_map<int, int> mp;
vector<int> goods(N);
vector<int> level(N, 0);
int ans=0;
int n, m, k, s;
 
void bfs(int node)
{
	level[node]=0;
	queue<int> q;
	mp[goods[node]]++;
	q.push(node);
	while(!q.empty())
	{
		int tp=q.front();
		q.pop();
		visited[tp]=true;
		if(mp.find(goods[tp])==mp.end())
		{
			ans+=level[tp];
			mp[goods[tp]]++;
		}
		cout<<ans<<endl;
		if(mp.size()==s)
		{
			cout<<ans<<" ";
			return;
		}
		for(auto child: adj[tp])
		{
			if(!visited[child])
			{
				q.push(child);
				level[child]=level[tp]+1;
			}
		}
	}
}
 
void solve()
{
	cin>>n>>m>>k>>s;
	rep(i, n)
	{
		cin>>goods[i];
	}
	rep(i, m)
	{
		int u, v;
		cin>>u>>v;
		u--, v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i=0;i<n;i++)
	{
		ans=0;
		mp.clear();
		visited.clear();
		visited=vector<bool>(N, false);
		bfs(i);
	}
 
}
 
signed main() {
    // int t;cin>>t;while(t--)
	    solve();
 
 
return 0;
}

Full text and comments »

  • Vote: I like it
  • -1
  • Vote: I do not like it

By web_developer, history, 3 years ago, In English

Hello codeforces! I want help with this Codeforces Round #497 (Div. 1) A problem...Even after looking at the editorial I didn't understand why it's answer is n-x. Please help me understand.....Thanks!!

Upd: I don't care about downvotes, I just need an answer.

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it

By web_developer, history, 4 years ago, In English

Hello codeforces, I am the guy who spend more than 4 hours on the codeforces, But not solving problems, seeing Recent actions, standings, tourist's rating and other top coders most of the time. Someone would say, "It's rediculous", but I do. Any suggestions?

Full text and comments »

  • Vote: I like it
  • +104
  • Vote: I do not like it

By web_developer, 4 years ago, In English

Hello Codeforces community, hope all of you are doing good. I wanna ask, is seeing editorial of any problem that you can't solve after spending 15 minutes on it a bad habit? Please make me know if someone of you did this and became better because I am considering it a bad habit and I am despondent about it. All the suggestions are appreciated. Thanks!

Full text and comments »

  • Vote: I like it
  • +14
  • Vote: I do not like it