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 
. 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 -
CF glitch 
1 Like
