Help needed to Optimise More (Graph Problem 7)

Question

My_Solution

My complexity is : O (k(m+n)) (although it AC ) , but I have to solve in O (s(m+n))

Help @carre @galencolin @ssjgz @aneee004

I have written this:

Code
void solve() {
	int n, m, k, s;
	cin >> n >> m >> k >> s;
	vector<int> adj[n];
	int fruit[n];
	REP(n) cin >> fruit[i], fruit[i]--;
	for (int i = 0, u, v; i < m; i++) {
		cin >> u >> v;
		u--; v--;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	// track if a fruit has visited a node
	bool vis[n][k] = {};
	int cnt[n] = {}, cost[n] = {};
	// tuple of node, fruit type that is passing, distance it has travelled
	queue<tuple<int, int, int>> q;
	for(int i = 0; i < n; i++) {
		// he already has one fruit
		vis[i][fruit[i]] = 1;
		cnt[i]++;
		q.push(make_tuple(i, fruit[i], 0));
	}

	while(q.size()) {
		int u = get<0>(q.front());
		int curFruit = get<1>(q.front());
		int d = get<2>(q.front());
		q.pop();
		for(int v : adj[u]) {
		// if node v does not have the currect fruit that is passing u
		// and if v need more fruits
			if(not vis[v][curFruit] and cnt[v] < s) {
				cnt[v]++;
				// need to travel one edge from u to v, so +1
				cost[v] += d + 1;
				vis[v][curFruit] = 1;
				// fruit is currently at v, and has travelled d + 1 edges
				q.push(make_tuple(v, curFruit, d + 1));
			}
		}
	}
	for(int i = 0; i < n; i++) cout << cost[i] << " ";
	cout << "\n";
}

Each node has only s fruits visiting it, after which we terminate that BFS. So I guess it’s \mathcal O(s(n + m))? I’m not entirely convinced though.

[EDIT] This failed test 6 :sweat:. Let me know if you spot a bug.
[EDIT] Forgot to update visited. Now it’s accepted. I have edited the code above too.

3 Likes

What do you guys think? Is this \mathcal O(s(n + m))? The runtime was 904ms.

1 Like

I think u r correct it is O(s(n+m)) .

Btw what is this -

Screenshot_2020-07-22 aneee - Codeforces

CF glitch :face_with_raised_eyebrow:

1 Like

Lol. I got that bump in the contest yesterday. And it looks like they’re playing around with the submissions. Re-evaluating or something I guess.

What’s your codeforces handle btw?

1 Like