oj.uz

Submission #627980

# Submission time Handle Problem Language Result Execution time Memory
627980 2022-08-13T02:09:47 Z Do_you_copy Paths (RMI21_paths) C++17
100 / 100
 367 ms 19492 KB 
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 1e5 + 1;
int n, k;
multiset <ll, greater <ll>> S, Save;
//Save: stores edges which are deleted

vector <pii> adj[maxN];
ll dp[maxN];
int pos[maxN], pos2[maxN], max2[maxN];
ll ans[maxN];

void dfs0(int u, int p){
    for (auto i: adj[u]){
        if (i.fi == p) continue;
        dfs0(i.fi, u);
        if (dp[u] < dp[i.fi] + i.se){
            max2[u] = dp[u];
            pos2[u] = pos[u];
            dp[u] = dp[i.fi] + i.se;
            pos[u] = i.fi;
        }
        else if (max2[u] < dp[i.fi] + i.se){
            max2[u] = dp[i.fi] + i.se;
            pos2[u] = i.fi;
        }
    }
    for (auto i: adj[u]){
        //if (u == 4) cerr << i.fi << " ";
        if (i.fi == p || i.fi == pos[u]) continue;
        S.insert(dp[i.fi] + i.se);
        //if (u == 4)
        //cerr << i.fi << " ?";
        //cerr << u << " " << dp[i.fi] + i.se << "?\n";
    }
    if (u == p) S.insert(dp[u]);
}

ll sum = 0;
void add(ll x){
    if (S.size() < k){
        S.insert(x);
        sum += x;
        return;
    }
    auto it = S.end();
    --it;
    if (*it < x){
        sum -= *it;
        sum += x;
        Save.insert(*it);
        S.insert(x);
        S.erase(it);
    }
    else Save.insert(x);
}

void del(ll x){
    auto it = S.find(x);
    if (it != S.end()){
        sum -= x;
        S.erase(it);
        if (Save.empty()) return;
        auto it1 = Save.begin();
        sum += *it1;
        S.insert(*it1);
        Save.erase(it1);
    }
    else{
        it = Save.find(x);
        if (it != Save.end()) Save.erase(it);
    }
}

void dfs(int u, int p, int d){
    ans[u] = sum;
    for (auto i: adj[u]){
        if (i.fi == p) continue;
        ans[i.fi] = ans[u];
        ll maxx = 0;
        if (i.fi == pos[u]){
            if (pos2[u]) maxx = max(d, max2[u]);
            else maxx = d;
        }
        else maxx = max(d, dp[u]);
        maxx += i.se;
        add(maxx);
        del(maxx - i.se);
        add(dp[i.fi]);
        del(dp[i.fi] + i.se);
        dfs(i.fi, u, maxx);
        del(maxx);
        add(maxx - i.se);
        del(dp[i.fi]);
        add(dp[i.fi] + i.se);
    }
}

void Init(){
    cin >> n >> k;
    for (int i = 1; i < n; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    dfs0(1, 1);
    for (auto i: S) ans[1] += i;
    while (S.size() > k){
        auto it = S.end(); --it;
        ans[1] -= *it;
        Save.insert(*it);
        S.erase(it);
    }
    sum = ans[1];
    dfs(1, 1, 0);
    for (int i = 1; i <= n; ++i){
        cout << ans[i] << "\n";
    }
}

#define debu
#define taskname "test"
signed main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        #ifdef debug
        freopen(taskname".out", "w", stdout);
        #endif
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
    if (fopen("timeout.txt", "r")){
        ofstream timeout("timeout.txt");
        timeout << 1000 * double(clock()) / CLOCKS_PER_SEC;
        #ifndef debug
        cerr << "\nTime elapsed: " << 1000 * double(clock()) / CLOCKS_PER_SEC << "ms\n";
        #endif
    }
}

Compilation message

Main.cpp: In function 'void add(ll)':
Main.cpp:66:18: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   66 |     if (S.size() < k){
      |         ~~~~~~~~~^~~
Main.cpp: In function 'void Init()':
Main.cpp:134:21: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  134 |     while (S.size() > k){
      |            ~~~~~~~~~^~~
Main.cpp: In function 'int main()':
Main.cpp:151:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2692 KB Output is correct
8 Correct 3 ms 2820 KB Output is correct
9 Correct 4 ms 2828 KB Output is correct
10 Correct 4 ms 2772 KB Output is correct
11 Correct 4 ms 2772 KB Output is correct
12 Correct 3 ms 2824 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2692 KB Output is correct
8 Correct 3 ms 2820 KB Output is correct
9 Correct 4 ms 2828 KB Output is correct
10 Correct 4 ms 2772 KB Output is correct
11 Correct 4 ms 2772 KB Output is correct
12 Correct 3 ms 2824 KB Output is correct
13 Correct 5 ms 2900 KB Output is correct
14 Correct 5 ms 3028 KB Output is correct
15 Correct 4 ms 2944 KB Output is correct
16 Correct 6 ms 2900 KB Output is correct
17 Correct 6 ms 2956 KB Output is correct
18 Correct 4 ms 2900 KB Output is correct
19 Correct 5 ms 2952 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 15260 KB Output is correct
2 Correct 223 ms 19012 KB Output is correct
3 Correct 161 ms 15152 KB Output is correct
4 Correct 240 ms 17192 KB Output is correct
5 Correct 251 ms 18168 KB Output is correct
6 Correct 265 ms 17280 KB Output is correct

Subtask #6
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2692 KB Output is correct
8 Correct 3 ms 2820 KB Output is correct
9 Correct 4 ms 2828 KB Output is correct
10 Correct 4 ms 2772 KB Output is correct
11 Correct 4 ms 2772 KB Output is correct
12 Correct 3 ms 2824 KB Output is correct
13 Correct 5 ms 2900 KB Output is correct
14 Correct 5 ms 3028 KB Output is correct
15 Correct 4 ms 2944 KB Output is correct
16 Correct 6 ms 2900 KB Output is correct
17 Correct 6 ms 2956 KB Output is correct
18 Correct 4 ms 2900 KB Output is correct
19 Correct 5 ms 2952 KB Output is correct
20 Correct 234 ms 15260 KB Output is correct
21 Correct 223 ms 19012 KB Output is correct
22 Correct 161 ms 15152 KB Output is correct
23 Correct 240 ms 17192 KB Output is correct
24 Correct 251 ms 18168 KB Output is correct
25 Correct 265 ms 17280 KB Output is correct
26 Correct 367 ms 17676 KB Output is correct
27 Correct 297 ms 19096 KB Output is correct
28 Correct 332 ms 19492 KB Output is correct
29 Correct 170 ms 15400 KB Output is correct
30 Correct 347 ms 17576 KB Output is correct
31 Correct 299 ms 16164 KB Output is correct
32 Correct 299 ms 18352 KB Output is correct
33 Correct 302 ms 17616 KB Output is correct
34 Correct 144 ms 15112 KB Output is correct
35 Correct 321 ms 17636 KB Output is correct
36 Correct 237 ms 19400 KB Output is correct