oj.uz

Submission #761121

# Submission time Handle Problem Language Result Execution time Memory
761121 2023-06-19T08:22:31 Z keta_tsimakuridze Paths (RMI21_paths) C++17
100 / 100
 194 ms 21184 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t, ans[N], mx[N], sum, k;
vector<pii> V[N];
multiset<int> s1, s2;
void add(int x) {
    s2.insert(x);
    sum += x;
    if(s2.size() > k) {
        sum -= *s2.begin();
        s1.insert(*s2.begin());
        s2.erase(s2.find(*s2.begin()));
    }
}
void rem(int x) {
    if(s2.find(x) != s2.end()) {
        s2.erase(s2.find(x));
        sum -= x;
    } else assert(s1.find(x) != s1.end()), s1.erase(s1.find(x));
    if(s2.size() < k && s1.size()) {
        sum += *--s1.end();
        s2.insert(*--s1.end());
        s1.erase(s1.find(*--s1.end()));
    }
}
void dfs(int u, int p) {
    for(int i = 0; i < V[u].size(); i++) {
        int v = V[u][i].f, c = V[u][i].s;
        if(v == p) continue;
        dfs(v, u);
        mx[u] = max(mx[u], mx[v] + c);
    }
    int F = 0;
    for(int i = 0; i < V[u].size(); i++) {
        int v = V[u][i].f, c = V[u][i].s;
        if(v == p) continue;
        if(mx[u] != mx[v] + c || F) {
            add(mx[v] + c);
        }
        else F = 1;
    }
}
void reroot(int u, int p, int up) {
    ans[u] = sum;
    vector<int> MX = {up, -(int)1e15};
    for(auto x : V[u]) {
        int v = x.f, c = x.s;
        if(v == p) continue;
        if(mx[v] + c > MX[0]) {
            swap(MX[0], MX[1]);
            MX[0] = mx[v] + c;
        } else MX[1] = max(MX[1], mx[v] + c);
    }

    for(auto x : V[u]) {
        int v = x.f, c = x.s;
        if(v == p) continue;
        int X = (mx[v] + c == MX[0] ? MX[1] : MX[0]);
        if(X >= 0) rem(X), add(X + c);
        rem(mx[v] + c); add(mx[v]);
        reroot(v, u, X + c);
        rem(mx[v]), add(mx[v] + c);
        if(X >= 0) rem(X + c), add(X);
    }
}
main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n;
    cin >> n >> k;
    for(int i = 2; i <= n; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        V[u].push_back({v, c});
        V[v].push_back({u, c});
    }

    dfs(1, 0);
    add(mx[1]); add(0);
    reroot(1, 0, -0);
    for(int i = 1; i <= n; i++) cout << ans[i] << " ";
 }

Compilation message

Main.cpp: In function 'void add(long long int)':
Main.cpp:14:18: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   14 |     if(s2.size() > k) {
      |        ~~~~~~~~~~^~~
Main.cpp: In function 'void rem(long long int)':
Main.cpp:25:18: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   25 |     if(s2.size() < k && s1.size()) {
      |        ~~~~~~~~~~^~~
Main.cpp: In function 'void dfs(long long int, long long int)':
Main.cpp:32:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
Main.cpp:39:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:71:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   71 | main(){
      | ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 4 ms 5172 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 4 ms 5076 KB Output is correct
12 Correct 3 ms 5044 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 4 ms 5172 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 4 ms 5076 KB Output is correct
12 Correct 3 ms 5044 KB Output is correct
13 Correct 5 ms 5204 KB Output is correct
14 Correct 5 ms 5372 KB Output is correct
15 Correct 4 ms 5168 KB Output is correct
16 Correct 5 ms 5172 KB Output is correct
17 Correct 5 ms 5220 KB Output is correct
18 Correct 4 ms 5204 KB Output is correct
19 Correct 5 ms 5204 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 15244 KB Output is correct
2 Correct 164 ms 18108 KB Output is correct
3 Correct 130 ms 13096 KB Output is correct
4 Correct 161 ms 15124 KB Output is correct
5 Correct 153 ms 16436 KB Output is correct
6 Correct 177 ms 15196 KB Output is correct

Subtask #6
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 4 ms 5172 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 4 ms 5076 KB Output is correct
12 Correct 3 ms 5044 KB Output is correct
13 Correct 5 ms 5204 KB Output is correct
14 Correct 5 ms 5372 KB Output is correct
15 Correct 4 ms 5168 KB Output is correct
16 Correct 5 ms 5172 KB Output is correct
17 Correct 5 ms 5220 KB Output is correct
18 Correct 4 ms 5204 KB Output is correct
19 Correct 5 ms 5204 KB Output is correct
20 Correct 154 ms 15244 KB Output is correct
21 Correct 164 ms 18108 KB Output is correct
22 Correct 130 ms 13096 KB Output is correct
23 Correct 161 ms 15124 KB Output is correct
24 Correct 153 ms 16436 KB Output is correct
25 Correct 177 ms 15196 KB Output is correct
26 Correct 194 ms 17724 KB Output is correct
27 Correct 180 ms 20180 KB Output is correct
28 Correct 174 ms 20756 KB Output is correct
29 Correct 128 ms 15308 KB Output is correct
30 Correct 191 ms 17612 KB Output is correct
31 Correct 176 ms 16172 KB Output is correct
32 Correct 188 ms 18816 KB Output is correct
33 Correct 175 ms 17628 KB Output is correct
34 Correct 113 ms 15148 KB Output is correct
35 Correct 178 ms 17600 KB Output is correct
36 Correct 167 ms 21184 KB Output is correct