Link
I tried solving this using the ordered_set gnu pbds
I did dfs along with using swap and move methods for merging the sets of each node's children. The time complexity should be nlogn but why is it giving TLE on test 15?
dfs function
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Link
I tried solving this using the ordered_set gnu pbds
I did dfs along with using swap and move methods for merging the sets of each node's children. The time complexity should be nlogn but why is it giving TLE on test 15?
ordered_set dfs(int p, int e) {
d[p] = w[p] + d[e];
ordered_set ret;
for (auto u : adj[p]) {
if (u != e) {
auto x = dfs(u, p);
if (x.size() > ret.size()) {
swap(x, ret);
}
for (auto u : x) {
ret.insert(u);
}
}
}
//compute the answer for nope p
ans[p] = ret.order_of_key({d[p], INF});
ret.insert({d[p] - a[p], p});
return move(ret);
}
Name |
---|
Don't act like you really know how
move
works like, it's much more difficult than one can imagine. Read this.Okay move function doesn't work here but is there any way to make this approach work?
Just don't call
move
explicitly, usereturn ret;
.x.swap(ret)
. I also believe that ordered_set is not the intended solution anyway.and
move
is useless hereThanks, this worked!