Submission #627980

#	Time	Username	Problem	Language	Result	Execution time	Memory
627980		Do_you_copy	Paths (RMI21_paths)	C++17	100 / 100	367 ms	19492 KiB

Main

#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 (stderr)

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 / 8
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 12 / 12
• Subtask 6: 32 / 32