web_developer's blog

By web_developer, history, 6 weeks 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;
}
 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Hello web developer. Please, help others to help you. Don't only throw your code and one question link, asking what is wrong. Firstly, you must explain the problem and explain your approach.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by web_developer (previous revision, new revision, compare).